Copyright	(c) Conal Elliott 2008-2012
License	BSD3
Maintainer	conal@conal.net
Stability	experimental
Safe Haskell	Safe
Language	Haskell2010

Data.MemoTrie

Description

Trie-based memoizer

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

You can automatically derive generic instances. for example:

{--}
import Data.MemoTrie
import GHC.Generics (Generic) 

data Color = RGB Int Int Int
           | NamedColor String 
 deriving (Generic) 

instance HasTrie Color where
  newtype (Color :->: b) = ColorTrie { unColorTrie :: Reg Color :->: b } 
  trie = trieGeneric ColorTrie 
  untrie = untrieGeneric unColorTrie
  enumerate = enumerateGeneric unColorTrie

see examples/Generic.hs, which can be run with:

cabal configure -fexamples && cabal run generic

Synopsis

Documentation

class HasTrie a where

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

Associated Types

data (:->:) a :: * -> * infixr 0

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 (V1 x)	just like `void`
HasTrie (U1 x)	just like `()`
(HasTrie a, HasTrie b) => HasTrie (Either a b)
(HasTrie a, HasTrie b) => HasTrie (a, b)
HasTrie a => HasTrie (K1 i a x)	wraps `a`
(HasTrie (f x), HasTrie (g x)) => HasTrie ((:+:) f g x)	wraps `Either (f x) (g x)`
(HasTrie (f x), HasTrie (g x)) => HasTrie ((:*:) f g x)	wraps `(f x, g x)`
(HasTrie a, HasTrie b, HasTrie c) => HasTrie (a, b, c)
HasTrie (f x) => HasTrie (M1 i t f x)	wraps `f x`

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 infixr 9

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

trieGeneric :: (Generic a, HasTrie (Reg a)) => ((Reg a :->: b) -> a :->: b) -> (a -> b) -> a :->: b

Generic-friendly default for trie

untrieGeneric :: (Generic a, HasTrie (Reg a)) => ((a :->: b) -> Reg a :->: b) -> (a :->: b) -> a -> b

Generic-friendly default for untrie

enumerateGeneric :: (Generic a, HasTrie (Reg a)) => ((a :->: b) -> Reg a :->: b) -> (a :->: b) -> [(a, b)]

Generic-friendly default for enumerate

type Reg a = Rep a ()

the data type in a regular form. "unlifted" generic representation. (i.e. is a unary type constructor).

memoFix :: HasTrie a => ((a -> b) -> a -> b) -> a -> b

Memoizing recursion. Use like fix.