Data.MemoTrie

Trie-based memoizer

Adapted from sjanssen's paste: "a lazy trie" http://hpaste.org/3839, which I think is based on Ralf Hinze's paper Memo Functions, Polytypically!.

Documentation

class HasTrie a where

Mapping from all elements of a to the results of some function

Associated Types

data :->: a :: * -> *

Representation of trie with domain type a

Methods

trie :: (a -> b) -> a :->: b

Create the trie for the entire domain of a function

untrie :: (a :->: b) -> a -> b

Convert a trie to a function, i.e., access a field of the trie

enumerate :: (a :->: b) -> [(a, b)]

List the trie elements. Order of keys (:: a) is always the same.

Instances

HasTrie Bool

HasTrie Char

HasTrie Int

HasTrie Int8

HasTrie Int16

HasTrie Int32

HasTrie Int64

HasTrie Integer

HasTrie Word

HasTrie Word8

HasTrie Word16

HasTrie Word32

HasTrie Word64

HasTrie ()

HasTrie Void

HasTrie x => HasTrie [x]

(HasTrie a, HasTrie b) => HasTrie (Either a b)

(HasTrie a, HasTrie b) => HasTrie (a, b)

(HasTrie a, HasTrie b, HasTrie c) => HasTrie (a, b, c)

domain :: HasTrie a => [a]

Domain elements of a trie

idTrie :: HasTrie a => a :->: a

Identity trie

(@.@) :: (HasTrie a, HasTrie b) => (b :->: c) -> (a :->: b) -> a :->: c

Trie composition

memo :: HasTrie t => (t -> a) -> t -> a

Trie-based function memoizer

memo2 :: (HasTrie s, HasTrie t) => (s -> t -> a) -> s -> t -> a

Memoize a binary function, on its first argument and then on its second. Take care to exploit any partial evaluation.

memo3 :: (HasTrie r, HasTrie s, HasTrie t) => (r -> s -> t -> a) -> r -> s -> t -> a

Memoize a ternary function on successive arguments. Take care to exploit any partial evaluation.

mup :: HasTrie t => (b -> c) -> (t -> b) -> t -> c

Lift a memoizer to work with one more argument.

inTrie :: (HasTrie a, HasTrie c) => ((a -> b) -> c -> d) -> (a :->: b) -> c :->: d

Apply a unary function inside of a trie

inTrie2 :: (HasTrie a, HasTrie c, HasTrie e) => ((a -> b) -> (c -> d) -> e -> f) -> (a :->: b) -> (c :->: d) -> e :->: f

Apply a binary function inside of a trie

inTrie3 :: (HasTrie a, HasTrie c, HasTrie e, HasTrie g) => ((a -> b) -> (c -> d) -> (e -> f) -> g -> h) -> (a :->: b) -> (c :->: d) -> (e :->: f) -> g :->: h

Apply a ternary function inside of a trie