MemoTrie-0.6.11: Trie-based memo functions

Copyright | (c) Conal Elliott 2008-2016
License | BSD3
Maintainer | conal@conal.net
Stability | experimental
Safe Haskell | Safe-Inferred
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:

    {-# LANGUAGE DeriveGeneric, TypeOperators, TypeFamilies #-}
    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

- class HasTrie a where
  - data (:->:) a :: Type -> Type
  - trie :: (a -> b) -> a :->: b
  - untrie :: (a :->: b) -> a -> b
  - enumerate :: (a :->: b) -> [(a, b)]
- data family (:->:) a :: Type -> Type
- 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
- 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 ()
- memoFix :: HasTrie a => ((a -> b) -> a -> b) -> a -> b

# Documentation

class HasTrie a where Source #

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

Associated Types

data (:->:) a :: Type -> Type infixr 0 Source #

Representation of trie with domain type `a`

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

Instances details

HasTrie Void Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

data Void :->: a |
Instance details Defined in Data.MemoTrie data Void :->: a = VoidTrie

Methods

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

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

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

HasTrie Int16 Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype Int16 :->: a |
Instance details Defined in Data.MemoTrie newtype Int16 :->: a = Int16Trie (Word16 :->: a)

Methods

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

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

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

HasTrie Int32 Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype Int32 :->: a |
Instance details Defined in Data.MemoTrie newtype Int32 :->: a = Int32Trie (Word32 :->: a)

Methods

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

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

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

HasTrie Int64 Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype Int64 :->: a |
Instance details Defined in Data.MemoTrie newtype Int64 :->: a = Int64Trie (Word64 :->: a)

Methods

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

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

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

HasTrie Int8 Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype Int8 :->: a |
Instance details Defined in Data.MemoTrie newtype Int8 :->: a = Int8Trie (Word8 :->: a)

Methods

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

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

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

HasTrie Word16 Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype Word16 :->: a |
Instance details Defined in Data.MemoTrie newtype Word16 :->: a = Word16Trie ([Bool] :->: a)

Methods

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

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

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

HasTrie Word32 Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype Word32 :->: a |
Instance details Defined in Data.MemoTrie newtype Word32 :->: a = Word32Trie ([Bool] :->: a)

Methods

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

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

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

HasTrie Word64 Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype Word64 :->: a |
Instance details Defined in Data.MemoTrie newtype Word64 :->: a = Word64Trie ([Bool] :->: a)

Methods

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

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

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

HasTrie Word8 Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype Word8 :->: a |
Instance details Defined in Data.MemoTrie newtype Word8 :->: a = Word8Trie ([Bool] :->: a)

Methods

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

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

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

HasTrie Integer Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype Integer :->: a |
Instance details Defined in Data.MemoTrie newtype Integer :->: a = IntegerTrie ((Bool, [Bool]) :->: a)

Methods

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

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

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

HasTrie () Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype () :->: a |
Instance details Defined in Data.MemoTrie newtype () :->: a = UnitTrie a

Methods

trie :: (() -> b) -> () :->: b Source #

untrie :: (() :->: b) -> () -> b Source #

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

HasTrie Bool Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

data Bool :->: x |
Instance details Defined in Data.MemoTrie data Bool :->: x = BoolTrie x x

Methods

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

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

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

HasTrie Char Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype Char :->: a |
Instance details Defined in Data.MemoTrie newtype Char :->: a = CharTrie (Int :->: a)

Methods

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

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

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

HasTrie Int Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype Int :->: a |
Instance details Defined in Data.MemoTrie newtype Int :->: a = IntTrie (Word :->: a)

Methods

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

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

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

HasTrie Word Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype Word :->: a |
Instance details Defined in Data.MemoTrie newtype Word :->: a = WordTrie ([Bool] :->: a)

Methods

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

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

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

HasTrie a => HasTrie (Maybe a) Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

data (Maybe a) :->: b |
Instance details Defined in Data.MemoTrie data (Maybe a) :->: b = MaybeTrie b (a :->: b)

Methods

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

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

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

HasTrie x => HasTrie [x] Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype [x] :->: a |
Instance details Defined in Data.MemoTrie newtype [x] :->: a = ListTrie (Either () (x, [x]) :->: a)

Methods

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

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

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

(HasTrie a, HasTrie b) => HasTrie (Either a b) Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

data (Either a b) :->: x |
Instance details Defined in Data.MemoTrie data (Either a b) :->: x = EitherTrie (a :->: x) (b :->: x)

Methods

trie :: (Either a b -> b0) -> Either a b :->: b0 Source #

untrie :: (Either a b :->: b0) -> Either a b -> b0 Source #

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

HasTrie (U1 x) Source # | just like `()`

Instance details

Defined in Data.MemoTrie

Associated Types

newtype (U1 x) :->: b |
Instance details Defined in Data.MemoTrie newtype (U1 x) :->: b = U1Trie b

Methods

trie :: (U1 x -> b) -> U1 x :->: b Source #

untrie :: (U1 x :->: b) -> U1 x -> b Source #

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

HasTrie (V1 x) Source # | just like `void`

Instance details

Defined in Data.MemoTrie

Associated Types

data (V1 x) :->: b |
Instance details Defined in Data.MemoTrie data (V1 x) :->: b = V1Trie

Methods

trie :: (V1 x -> b) -> V1 x :->: b Source #

untrie :: (V1 x :->: b) -> V1 x -> b Source #

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

(HasTrie a, HasTrie b) => HasTrie (a, b) Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype (a, b) :->: x |
Instance details Defined in Data.MemoTrie newtype (a, b) :->: x = PairTrie (a :->: (b :->: x))

Methods

trie :: ((a, b) -> b0) -> (a, b) :->: b0 Source #

untrie :: ((a, b) :->: b0) -> (a, b) -> b0 Source #

enumerate :: ((a, b) :->: b0) -> [((a, b), b0)] Source #

(HasTrie a, HasTrie b, HasTrie c) => HasTrie (a, b, c) Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

newtype (a, b, c) :->: x |
Instance details Defined in Data.MemoTrie newtype (a, b, c) :->: x = TripleTrie (((a, b), c) :->: x)

Methods

trie :: ((a, b, c) -> b0) -> (a, b, c) :->: b0 Source #

untrie :: ((a, b, c) :->: b0) -> (a, b, c) -> b0 Source #

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

(HasTrie (f x), HasTrie (g x)) => HasTrie ((f :*: g) x) Source # | wraps `(f x, g x)`

Instance details

Defined in Data.MemoTrie

Associated Types

newtype ((f :*: g) x) :->: b |
Instance details Defined in Data.MemoTrie newtype ((f :*: g) x) :->: b = PairTrie1 ((f x, g x) :->: b)

Methods

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

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

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

(HasTrie (f x), HasTrie (g x)) => HasTrie ((f :+: g) x) Source # | wraps `Either (f x) (g x)`

Instance details

Defined in Data.MemoTrie

Associated Types

newtype ((f :+: g) x) :->: b |
Instance details Defined in Data.MemoTrie newtype ((f :+: g) x) :->: b = EitherTrie1 (Either (f x) (g x) :->: b)

Methods

trie :: ((f :+: g) x -> b) -> (f :+: g) x :->: b Source #

untrie :: ((f :+: g) x :->: b) -> (f :+: g) x -> b Source #

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

HasTrie a => HasTrie (K1 i a x) Source # | wraps `a`

Instance details

Defined in Data.MemoTrie

Associated Types

newtype (K1 i a x) :->: b |
Instance details Defined in Data.MemoTrie newtype (K1 i a x) :->: b = K1Trie (a :->: b)

Methods

trie :: (K1 i a x -> b) -> K1 i a x :->: b Source #

untrie :: (K1 i a x :->: b) -> K1 i a x -> b Source #

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

HasTrie (f x) => HasTrie (M1 i t f x) Source # | wraps `f x`

Instance details

Defined in Data.MemoTrie

Associated Types

newtype (M1 i t f x) :->: b |
Instance details Defined in Data.MemoTrie newtype (M1 i t f x) :->: b = M1Trie (f x :->: b)

Methods

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

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

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

data family (:->:) a :: Type -> Type infixr 0 Source #

Representation of trie with domain type `a`

#### Instances

Instances details

HasTrie a => Applicative ((:->:) a) Source # |
Instance details Defined in Data.MemoTrie Methods pure :: a0 -> a :->: a0 Source # (<*>) :: (a :->: (a0 -> b)) -> (a :->: a0) -> a :->: b Source # liftA2 :: (a0 -> b -> c) -> (a :->: a0) -> (a :->: b) -> a :->: c Source # (*>) :: (a :->: a0) -> (a :->: b) -> a :->: b Source # (<*) :: (a :->: a0) -> (a :->: b) -> a :->: a0 Source #
HasTrie a => Functor ((:->:) a) Source # |
Instance details Defined in Data.MemoTrie Methods fmap :: (a0 -> b) -> (a :->: a0) -> a :->: b Source # (<$) :: a0 -> (a :->: b) -> a :->: a0 Source #
HasTrie a => Monad ((:->:) a) Source # |
Instance details Defined in Data.MemoTrie Methods (>>=) :: (a :->: a0) -> (a0 -> a :->: b) -> a :->: b Source # (>>) :: (a :->: a0) -> (a :->: b) -> a :->: b Source # return :: a0 -> a :->: a0 Source #
(HasTrie a, Monoid b) => Monoid (a :->: b) Source # |
Instance details Defined in Data.MemoTrie Methods mempty :: a :->: b Source # mappend :: (a :->: b) -> (a :->: b) -> a :->: b Source # mconcat :: [a :->: b] -> a :->: b Source #
(HasTrie a, Semigroup b) => Semigroup (a :->: b) Source # |
Instance details Defined in Data.MemoTrie Methods (<>) :: (a :->: b) -> (a :->: b) -> a :->: b Source # sconcat :: NonEmpty (a :->: b) -> a :->: b Source # stimes :: Integral b0 => b0 -> (a :->: b) -> a :->: b Source #
(HasTrie a, Show a, Show b) => Show (a :->: b) Source # |
Instance details Defined in Data.MemoTrie Methods showsPrec :: Int -> (a :->: b) -> ShowS Source # show :: (a :->: b) -> String Source # showList :: [a :->: b] -> ShowS Source #
(HasTrie a, Eq b) => Eq (a :->: b) Source # |
Instance details Defined in Data.MemoTrie Methods (==) :: (a :->: b) -> (a :->: b) -> Bool Source # (/=) :: (a :->: b) -> (a :->: b) -> Bool Source #
Newtype (Void :->: a) Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

type O (Void :->: a) |
Instance details Defined in Data.MemoTrie type O (Void :->: a) = ()

Methods

pack :: O (Void :->: a) -> Void :->: a Source #

unpack :: (Void :->: a) -> O (Void :->: a) Source #

Newtype (Either a b :->: x) Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

type O (Either a b :->: x) |
Instance details Defined in Data.MemoTrie type O (Either a b :->: x) = (a :->: x, b :->: x)

Methods

pack :: O (Either a b :->: x) -> Either a b :->: x Source #

unpack :: (Either a b :->: x) -> O (Either a b :->: x) Source #

Newtype (Maybe a :->: x) Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

type O (Maybe a :->: x) |
Instance details Defined in Data.MemoTrie type O (Maybe a :->: x) = (x, a :->: x)

Methods

pack :: O (Maybe a :->: x) -> Maybe a :->: x Source #

unpack :: (Maybe a :->: x) -> O (Maybe a :->: x) Source #

Newtype ((a, b) :->: x) Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

type O ((a, b) :->: x) |
Instance details Defined in Data.MemoTrie type O ((a, b) :->: x) = a :->: (b :->: x)

Methods

pack :: O ((a, b) :->: x) -> (a, b) :->: x Source #

unpack :: ((a, b) :->: x) -> O ((a, b) :->: x) Source #

Newtype (() :->: a) Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

type O (() :->: a) |
Instance details Defined in Data.MemoTrie type O (() :->: a) = a

Methods

pack :: O (() :->: a) -> () :->: a Source #

unpack :: (() :->: a) -> O (() :->: a) Source #

Newtype (Bool :->: a) Source # |

Instance details

Defined in Data.MemoTrie

Associated Types

type O (Bool :->: a) |
Instance details Defined in Data.MemoTrie type O (Bool :->: a) = (a, a)

Methods

pack :: O (Bool :->: a) -> Bool :->: a Source #

unpack :: (Bool :->: a) -> O (Bool :->: a) Source #

data Void :->: a Source # |
Instance details Defined in Data.MemoTrie data Void :->: a = VoidTrie
newtype Int16 :->: a Source # |
Instance details Defined in Data.MemoTrie newtype Int16 :->: a = Int16Trie (Word16 :->: a)
newtype Int32 :->: a Source # |
Instance details Defined in Data.MemoTrie newtype Int32 :->: a = Int32Trie (Word32 :->: a)
newtype Int64 :->: a Source # |
Instance details Defined in Data.MemoTrie newtype Int64 :->: a = Int64Trie (Word64 :->: a)
newtype Int8 :->: a Source # |
Instance details Defined in Data.MemoTrie newtype Int8 :->: a = Int8Trie (Word8 :->: a)
newtype Word16 :->: a Source # |
Instance details Defined in Data.MemoTrie newtype Word16 :->: a = Word16Trie ([Bool] :->: a)
newtype Word32 :->: a Source # |
Instance details Defined in Data.MemoTrie newtype Word32 :->: a = Word32Trie ([Bool] :->: a)
newtype Word64 :->: a Source # |
Instance details Defined in Data.MemoTrie newtype Word64 :->: a = Word64Trie ([Bool] :->: a)
newtype Word8 :->: a Source # |
Instance details Defined in Data.MemoTrie newtype Word8 :->: a = Word8Trie ([Bool] :->: a)
newtype Integer :->: a Source # |
Instance details Defined in Data.MemoTrie newtype Integer :->: a = IntegerTrie ((Bool, [Bool]) :->: a)
newtype () :->: a Source # |
Instance details Defined in Data.MemoTrie newtype () :->: a = UnitTrie a
data Bool :->: x Source # |
Instance details Defined in Data.MemoTrie data Bool :->: x = BoolTrie x x
newtype Char :->: a Source # |
Instance details Defined in Data.MemoTrie newtype Char :->: a = CharTrie (Int :->: a)
newtype Int :->: a Source # |
Instance details Defined in Data.MemoTrie newtype Int :->: a = IntTrie (Word :->: a)
newtype Word :->: a Source # |
Instance details Defined in Data.MemoTrie newtype Word :->: a = WordTrie ([Bool] :->: a)
data (Maybe a) :->: b Source # |
Instance details Defined in Data.MemoTrie data (Maybe a) :->: b = MaybeTrie b (a :->: b)
newtype [x] :->: a Source # |
Instance details Defined in Data.MemoTrie newtype [x] :->: a = ListTrie (Either () (x, [x]) :->: a)
data (Either a b) :->: x Source # |
Instance details Defined in Data.MemoTrie data (Either a b) :->: x = EitherTrie (a :->: x) (b :->: x)
newtype (U1 x) :->: b Source # |
Instance details Defined in Data.MemoTrie newtype (U1 x) :->: b = U1Trie b
data (V1 x) :->: b Source # |
Instance details Defined in Data.MemoTrie data (V1 x) :->: b = V1Trie
newtype (a, b) :->: x Source # |
Instance details Defined in Data.MemoTrie newtype (a, b) :->: x = PairTrie (a :->: (b :->: x))
type O (Void :->: a) Source # |
Instance details Defined in Data.MemoTrie type O (Void :->: a) = ()
type O (Either a b :->: x) Source # |
Instance details Defined in Data.MemoTrie type O (Either a b :->: x) = (a :->: x, b :->: x)
type O (Maybe a :->: x) Source # |
Instance details Defined in Data.MemoTrie type O (Maybe a :->: x) = (x, a :->: x)
type O ((a, b) :->: x) Source # |
Instance details Defined in Data.MemoTrie type O ((a, b) :->: x) = a :->: (b :->: x)
type O (() :->: a) Source # |
Instance details Defined in Data.MemoTrie type O (() :->: a) = a
type O (Bool :->: a) Source # |
Instance details Defined in Data.MemoTrie type O (Bool :->: a) = (a, a)
newtype (a, b, c) :->: x Source # |
Instance details Defined in Data.MemoTrie newtype (a, b, c) :->: x = TripleTrie (((a, b), c) :->: x)
newtype ((f :*: g) x) :->: b Source # |
Instance details Defined in Data.MemoTrie newtype ((f :*: g) x) :->: b = PairTrie1 ((f x, g x) :->: b)
newtype ((f :+: g) x) :->: b Source # |
Instance details Defined in Data.MemoTrie newtype ((f :+: g) x) :->: b = EitherTrie1 (Either (f x) (g x) :->: b)
newtype (K1 i a x) :->: b Source # |
Instance details Defined in Data.MemoTrie newtype (K1 i a x) :->: b = K1Trie (a :->: b)
newtype (M1 i t f x) :->: b Source # |
Instance details Defined in Data.MemoTrie newtype (M1 i t f x) :->: b = M1Trie (f x :->: b)

domain :: HasTrie a => [a] Source #

Domain elements of a trie

idTrie :: HasTrie a => a :->: a Source #

Identity trie

(@.@) :: (HasTrie a, HasTrie b) => (b :->: c) -> (a :->: b) -> a :->: c infixr 9 Source #

Trie composition

memo :: HasTrie t => (t -> a) -> t -> a Source #

Trie-based function memoizer

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

inTrie2 :: (HasTrie a, HasTrie c, HasTrie e) => ((a -> b) -> (c -> d) -> e -> f) -> (a :->: b) -> (c :->: d) -> e :->: f Source #

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 Source #

Apply a ternary function inside of a trie

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

`Generic`-friendly default for `trie`

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

`Generic`-friendly default for `untrie`

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

`Generic`-friendly default for `enumerate`

type Reg a = Rep a () Source #

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 Source #

Memoizing recursion. Use like `fix`.