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!".

You can automatically derive generic instances. for example:

-- LANGUAGE DeriveGeneric, TypeOperators  

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

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

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 ()

"unlifted" generic representation. (i.e. is a unary type constructor).