Data.MemoTrie

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

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

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

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

type Reg a = Rep a ()

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