Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

Data.Random.Choose provides an efficient mechanism to select *n* items
uniformly at random from an input stream, for some fixed *n*.

- Data.Random.Choose.Tree contains the implementation details.
- Data.Random.Choose.IO puts everything together as a single function (using IO).

# Algorithm outline

We store items on a binary tree (`Tree`

), moving them down the left or right
branch according to a coin flip. At the end, the rightmost *n* items on the tree
are selected. Each time we `insert`

into a tree having *n* items, we prune its
leftmost item (`applyLimit`

and `evict`

).

It may be helpful to think of this as lazily assigning each item a *d*-bit
score, where *d* is the maximum depth of the tree. Moving an item to the left
or right corresponds to appending a 0 or 1 to its score. Note that the laziness
is necessary, because *d* is not known a priori.

The process of moving items futher down the tree is referred to as
disambiguation (`disambiguate`

) because its purpose is to resolve ties in the
score.