wam

# WAM

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

## Installation

If [available in Hex](https://hex.pm/docs/publish), the package can be installed
by adding `wam` to your list of dependencies in `mix.exs`:

```elixir
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 **any**
`rng >= 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.

```elixir
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:

```elixir
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. 

  ```elixir
  {: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. 

  ```elixir
  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

  ```elixir
  {: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)`

  ```elixir
  :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](https://github.com/elixir-lang/ex_doc)
and published on [HexDocs](https://hexdocs.pm). Once published, the docs can
be found at <https://hexdocs.pm/wam>.