Data.MemoTrie

Trie-based memoizer Adapted from sjanssen's paste: "a lazy trie" http://hpaste.org/3839.

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

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 Int

HasTrie Integer

HasTrie Word

HasTrie ()

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