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

Minimal complete definition

trie, untrie, enumerate

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

Associated Types

data Bool :->: b :: *

Methods

trie :: (Bool -> b) -> Bool :->: b

untrie :: (Bool :->: b) -> Bool -> b

enumerate :: (Bool :->: b) -> [(Bool, b)]

HasTrie Char

Associated Types

data Char :->: b :: *

Methods

trie :: (Char -> b) -> Char :->: b

untrie :: (Char :->: b) -> Char -> b

enumerate :: (Char :->: b) -> [(Char, b)]

HasTrie Int

Associated Types

data Int :->: b :: *

Methods

trie :: (Int -> b) -> Int :->: b

untrie :: (Int :->: b) -> Int -> b

enumerate :: (Int :->: b) -> [(Int, b)]

HasTrie Int8

Associated Types

data Int8 :->: b :: *

Methods

trie :: (Int8 -> b) -> Int8 :->: b

untrie :: (Int8 :->: b) -> Int8 -> b

enumerate :: (Int8 :->: b) -> [(Int8, b)]

HasTrie Int16

Associated Types

data Int16 :->: b :: *

Methods

trie :: (Int16 -> b) -> Int16 :->: b

untrie :: (Int16 :->: b) -> Int16 -> b

enumerate :: (Int16 :->: b) -> [(Int16, b)]

HasTrie Int32

Associated Types

data Int32 :->: b :: *

Methods

trie :: (Int32 -> b) -> Int32 :->: b

untrie :: (Int32 :->: b) -> Int32 -> b

enumerate :: (Int32 :->: b) -> [(Int32, b)]

HasTrie Int64

Associated Types

data Int64 :->: b :: *

Methods

trie :: (Int64 -> b) -> Int64 :->: b

untrie :: (Int64 :->: b) -> Int64 -> b

enumerate :: (Int64 :->: b) -> [(Int64, b)]

HasTrie Integer

Associated Types

data Integer :->: b :: *

Methods

trie :: (Integer -> b) -> Integer :->: b

untrie :: (Integer :->: b) -> Integer -> b

enumerate :: (Integer :->: b) -> [(Integer, b)]

HasTrie Word

Associated Types

data Word :->: b :: *

Methods

trie :: (Word -> b) -> Word :->: b

untrie :: (Word :->: b) -> Word -> b

enumerate :: (Word :->: b) -> [(Word, b)]

HasTrie Word8

Associated Types

data Word8 :->: b :: *

Methods

trie :: (Word8 -> b) -> Word8 :->: b

untrie :: (Word8 :->: b) -> Word8 -> b

enumerate :: (Word8 :->: b) -> [(Word8, b)]

HasTrie Word16

Associated Types

data Word16 :->: b :: *

Methods

trie :: (Word16 -> b) -> Word16 :->: b

untrie :: (Word16 :->: b) -> Word16 -> b

enumerate :: (Word16 :->: b) -> [(Word16, b)]

HasTrie Word32

Associated Types

data Word32 :->: b :: *

Methods

trie :: (Word32 -> b) -> Word32 :->: b

untrie :: (Word32 :->: b) -> Word32 -> b

enumerate :: (Word32 :->: b) -> [(Word32, b)]

HasTrie Word64

Associated Types

data Word64 :->: b :: *

Methods

trie :: (Word64 -> b) -> Word64 :->: b

untrie :: (Word64 :->: b) -> Word64 -> b

enumerate :: (Word64 :->: b) -> [(Word64, b)]

HasTrie ()

Associated Types

data () :->: b :: *

Methods

trie :: (() -> b) -> () :->: b

untrie :: (() :->: b) -> () -> b

enumerate :: (() :->: b) -> [((), b)]

HasTrie Void

Associated Types

data Void :->: b :: *

Methods

trie :: (Void -> b) -> Void :->: b

untrie :: (Void :->: b) -> Void -> b

enumerate :: (Void :->: b) -> [(Void, b)]

HasTrie x => HasTrie [x]

Associated Types

data [x] :->: b :: *

Methods

trie :: ([x] -> b) -> [x] :->: b

untrie :: ([x] :->: b) -> [x] -> b

enumerate :: ([x] :->: b) -> [([x], b)]

HasTrie a => HasTrie (Maybe a)

Associated Types

data (Maybe a) :->: b :: *

Methods

trie :: (Maybe a -> b) -> Maybe a :->: b

untrie :: (Maybe a :->: b) -> Maybe a -> b

enumerate :: (Maybe a :->: b) -> [(Maybe a, b)]

(HasTrie a, HasTrie b) => HasTrie (Either a b)

Associated Types

data (Either a b) :->: b :: *

Methods

trie :: (Either a b -> b) -> Either a b :->: b

untrie :: (Either a b :->: b) -> Either a b -> b

enumerate :: (Either a b :->: b) -> [(Either a b, b)]

HasTrie (V1 * x)

just like void

Associated Types

data (V1 * x) :->: b :: *

Methods

trie :: (V1 * x -> b) -> V1 * x :->: b

untrie :: (V1 * x :->: b) -> V1 * x -> b

enumerate :: (V1 * x :->: b) -> [(V1 * x, b)]

HasTrie (U1 * x)

just like ()

Associated Types

data (U1 * x) :->: b :: *

Methods

trie :: (U1 * x -> b) -> U1 * x :->: b

untrie :: (U1 * x :->: b) -> U1 * x -> b

enumerate :: (U1 * x :->: b) -> [(U1 * x, b)]

(HasTrie a, HasTrie b) => HasTrie (a, b)

Associated Types

data (a, b) :->: b :: *

Methods

trie :: ((a, b) -> b) -> (a, b) :->: b

untrie :: ((a, b) :->: b) -> (a, b) -> b

enumerate :: ((a, b) :->: b) -> [((a, b), b)]

(HasTrie a, HasTrie b, HasTrie c) => HasTrie (a, b, c)

Associated Types

data (a, b, c) :->: b :: *

Methods

trie :: ((a, b, c) -> b) -> (a, b, c) :->: b

untrie :: ((a, b, c) :->: b) -> (a, b, c) -> b

enumerate :: ((a, b, c) :->: b) -> [((a, b, c), b)]

HasTrie a => HasTrie (K1 * i a x)

wraps a

Associated Types

data (K1 * i a x) :->: b :: *

Methods

trie :: (K1 * i a x -> b) -> K1 * i a x :->: b

untrie :: (K1 * i a x :->: b) -> K1 * i a x -> b

enumerate :: (K1 * i a x :->: b) -> [(K1 * i a x, b)]

(HasTrie (f x), HasTrie (g x)) => HasTrie ((:+:) * f g x)

wraps Either (f x) (g x)

Associated Types

data ((* :+: f) g x) :->: b :: *

Methods

trie :: ((* :+: f) g x -> b) -> (* :+: f) g x :->: b

untrie :: ((* :+: f) g x :->: b) -> (* :+: f) g x -> b

enumerate :: ((* :+: f) g x :->: b) -> [((* :+: f) g x, b)]

(HasTrie (f x), HasTrie (g x)) => HasTrie ((:*:) * f g x)

wraps (f x, g x)

Associated Types

data ((* :*: f) g x) :->: b :: *

Methods

trie :: ((* :*: f) g x -> b) -> (* :*: f) g x :->: b

untrie :: ((* :*: f) g x :->: b) -> (* :*: f) g x -> b

enumerate :: ((* :*: f) g x :->: b) -> [((* :*: f) g x, b)]

HasTrie (f x) => HasTrie (M1 * i t f x)

wraps f x

Associated Types

data (M1 * i t f x) :->: b :: *

Methods

trie :: (M1 * i t f x -> b) -> M1 * i t f x :->: b

untrie :: (M1 * i t f x :->: b) -> M1 * i t f x -> b

enumerate :: (M1 * i t f x :->: b) -> [(M1 * i t f x, b)]

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.