HORIZON HASKELLDocslts/ghc-9.10.x248f8f02026-10-05Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · 248f8f0 · 2026-10-05

ModuleMemoTrie-0.6.11Haskell2010

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: 

{-# 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
  • 1 type
  • 1 class
  • 14 values
  • PackageMemoTrie-0.6.11
  • Exports43
  • LanguageHaskell2010
  • LicenceBSD-3-Clause
  • SourceMemoTrie.hs
classclass HasTrie a where
#

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

Associated types

  • data family (:->:) a :: Type -> Type

    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.

Instances26HasTrie, …
familydata family (:->:) a :: Type -> Type
#

Representation of trie with domain type a

Instances45Monad, Functor, Applicative, Eq, Show, Semigroup, …
valuememo :: HasTrie t => (t -> a) -> t -> a
#

Trie-based function memoizer

valuememo2 :: (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.

valuememo3
  1. :: (HasTrie r, HasTrie s, HasTrie t)
  2. => r -> s -> t -> a
  3. -> r
  4. -> s
  5. -> t
  6. -> a
#

Memoize a ternary function on successive arguments. Take care to exploit any partial evaluation.

valuemup :: HasTrie t => (b -> c) -> (t -> b) -> t -> c
#

Lift a memoizer to work with one more argument.

typetype Reg a = Rep a ()
#

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

valuememoFix :: HasTrie a => ((a -> b) -> a -> b) -> a -> b
#

Memoizing recursion. Use like fix.