Stochastic memoization for the LazyPPL library. Stochastic memoization is a useful primitive for programming non-parametric models. It has type (a -> Prob b) -> Prob (a -> b), and can be thought of as simultaneously sampling results for all possible arguments, in a lazy way.

When a is enumerable, this amounts to converting a stream of probabilities to a random stream, which we can do by sampling each probability once.

This module provides:

• A general type-class MonadMemo for monads m that support memoization at certain argument types a.
• A default trie-based implementation when a is enumerable, and a curry-based implementation when a is a pair type.
• A general implementation generalmemoize for probability, using memo-tables.
• A memoized recursion combinator, memrec.

For illustrations, see the graph example, clustering, additive clustering, or the infinite relational model.