| Copyright | (c) Conal Elliott 2008-2012 |
|---|---|
| License | BSD3 |
| Maintainer | conal@conal.net |
| Stability | experimental |
| Safe Haskell | None |
| Language | Haskell98 |
Data.MemoTrie
Description
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!".
- class HasTrie a where
- domain :: HasTrie a => [a]
- idTrie :: HasTrie a => a :->: a
- (@.@) :: (HasTrie a, HasTrie b) => (b :->: c) -> (a :->: b) -> a :->: c
- memo :: HasTrie t => (t -> a) -> t -> a
- memo2 :: (HasTrie s, HasTrie t) => (s -> t -> a) -> s -> t -> a
- memo3 :: (HasTrie r, HasTrie s, HasTrie t) => (r -> s -> t -> a) -> r -> s -> t -> a
- mup :: HasTrie t => (b -> c) -> (t -> b) -> t -> c
- inTrie :: (HasTrie a, HasTrie c) => ((a -> b) -> c -> d) -> (a :->: b) -> c :->: d
- inTrie2 :: (HasTrie a, HasTrie c, HasTrie e) => ((a -> b) -> (c -> d) -> e -> f) -> (a :->: b) -> (c :->: d) -> e :->: f
- 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
Documentation
Mapping from all elements of a to the results of some function
Methods
trie :: (a -> b) -> a :->: b Source
Create the trie for the entire domain of a function
untrie :: (a :->: b) -> a -> b Source
Convert a trie to a function, i.e., access a field of the trie
enumerate :: (a :->: b) -> [(a, b)] Source
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) |
(@.@) :: (HasTrie a, HasTrie b) => (b :->: c) -> (a :->: b) -> a :->: c infixr 9 Source
Trie composition
memo2 :: (HasTrie s, HasTrie t) => (s -> t -> a) -> s -> t -> a Source
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 Source
Memoize a ternary function on successive arguments. Take care to exploit any partial evaluation.
mup :: HasTrie t => (b -> c) -> (t -> b) -> t -> c Source
Lift a memoizer to work with one more argument.
inTrie :: (HasTrie a, HasTrie c) => ((a -> b) -> c -> d) -> (a :->: b) -> c :->: d Source
Apply a unary function inside of a trie