WAM

Pure Elixir implementation of Walker's Alias Method (WAM). It's method for performing weighted random sampling.

Installation

If available in Hex, the package can be installed by adding wam to your list of dependencies in mix.exs:

def deps do
  [
    {:wam, "~> 0.3.0"}
  ]
end

Upgrading from 0.2.x

new/1 and new/2 now raise ArgumentError when the weights sum to 0. It used to answer a table instead, and that table drew uniformly over values every one of which had been muted. The bump is minor rather than patch because the change is breaking: where a caller got a structure back, it now gets an exception.

There is no honest table for that input. Muting by weight 0 works because the muted slot is paired away with a slot heavier than the mean; with no positive weight there is no heavy slot, nothing rewrites an alias, and every slot keeps the identity alias it started with. A slot aliased to itself is returned by the draw whatever probs holds, so unreachability — the very thing the weights asked for — is not a state the structure can express. Answering probs = 0.0 does not fix it; only refusing does.

Integer 0 and float 0.0 are the same case now. The old clause stood on a literal 0 in the head, which does not match 0.0, so float zeros fell through to the general clause and died with an ArithmeticError — one meaning, two incompatible behaviours.

A weight of 0 beside at least one positive weight is untouched and still mutes its slot by construction.

index/3 now checks the index in both directions. It used to guard only index < size, so a negative index reached elem/2 and raised ArgumentError instead of the {:error, :invalid_index} its spec promised — and through fetch/3 and get/4 the same. All four now answer the error tuple, and get/4 its default, for anything that is not an integer in [0, size). fetch_at/2 and at/3 already behaved this way.

Upgrading from 0.1.x

The meaning of the public probs field has flipped. It used to hold the probability of taking the alias; it now holds the probability of keeping the bucket, so a draw reads if rng < probs[i], do: i, else: aliases[i]. Sampling through fetch/3, get/4 and index/3 behaves exactly as before — only code that reads wam.probs directly, or that passes a hand-picked rng to steer the comparison, is affected.

The reason for the change is a guarantee: a zero-weight atom is always paired away, so its probs entry is exactly 0.0, and rng < 0.0 is false for anyrng >= 0. A weight of 0 is therefore unreachable by construction, no longer depending on the generator staying strictly below 1.0. Code that mutes content by weighting it 0 can rely on that.

If you were calling get(wam, index, sentinel_rng) to read a slot without drawing, use at/3 instead — see below.

Usage

It supports both weights and probabilities.

wam = WAM.new(%{a: 10, b: 4, c: 5})
wam = WAM.new(%{a: 10 / 19, b: 4 / 19, c: 5 / 19})

Also it supports list of tuples and two lists:

wam = WAM.new([{:a, 10}, {:b, 4}, {:c, 5}])
wam = WAM.new([:a, :b, :c], [10, 4, 5])

And provides three functions to work with random sampling:

• fetch(wam, index, random) - to get weighted value in form of {:ok, value} or return {:error, reason} tuple in case of error.

  {:ok, value} = WAM.fetch(wam, :rand.uniform(wam.size) - 1, :rand.uniform())
  {:error, reason} = WAM.fetch(wam, :rand.uniform(wam.size) + 1, :rand.uniform())
  

• fetch(wam, index, random, default \\ nil) - to get weighted value or default value in case of error. The default value is nil unless otherwise specified.

  value = WAM.get(wam, :rand.uniform(wam.size) - 1, :rand.uniform())
  nil = WAM.get(wam, :rand.uniform(wam.size) + 1, :rand.uniform())
  value = WAM.get(wam, :rand.uniform(wam.size) - 1, :rand.uniform(), :default)
  :default = WAM.get(wam, :rand.uniform(wam.size) + 1, :rand.uniform(), :default)
  

• index(wam, index, random) - to get weighted index in form of {:ok, value} or return {:error, reason} tuple in case of error

  {:ok, index} = WAM.fetch(wam, :rand.uniform(wam.size) - 1, :rand.uniform())
  {:error, reason} = WAM.fetch(wam, :rand.uniform(wam.size) + 1, :rand.uniform())
  

And two functions to read a slot without drawing at all:

• at(wam, index, default \\ nil) and fetch_at(wam, index)

  :a = WAM.at(wam, 0)
  {:ok, :a} = WAM.fetch_at(wam, 0)
  {:error, :invalid_index} = WAM.fetch_at(wam, wam.size)
  

  Reach for these rather than passing an rng picked to defeat the alias — that trick depends on how probs is oriented and breaks silently when it changes.

Documentation can be generated with ExDoc and published on HexDocs. Once published, the docs can be found at https://hexdocs.pm/wam.