Conal Elliott

Part one of this series introduced the problem of memoizing functions involving polymorphic recursion. The caching data structures used in memoization typically handle only one type of argument at a time. For instance, one can have finite maps of differing types, but each concrete finite map holds just one type of key and one type of value.

I extended memoization to handle polymorphic recursion by using an existential type together with a reified type of types. This extension works (afaik), but it is restricted to a particular form for the type of the polymorphic function being memoized, namely

-- Polymorphic function
type k :--> v = forall a. HasType a => k a -> v a

My motivating example is a GADT-based representation of typed lambda calculus, and some of the functions I want to memoize do not fit the pattern. After writing part one, I fooled around and found that I could transform these awkwardly typed polymorphic functions into isomorphic form that does indeed fit the restricted pattern of polymorphic types I can handle.

Continue reading ‘Memoizing polymorphic functions – part two’ »

Memoization takes a function and gives back a semantically equivalent function that reuses rather than recomputes when applied to the same argument more than once. Variations include not-quite-equivalence due to added strictness, and replacing value equality with pointer equality.

Memoization is often packaged up polymorphically:

memo :: (???) => (k -> v) -> (k -> v)

For pointer-based (“lazy”) memoization, the type constraint (“???”) is empty. For equality-based memoization, we’d need at least Eq k, and probably Ord k or HasTrie k for efficient lookup (in a finite map or a possibly infinite memo trie).

Although memo is polymorphic, its argument is a monomorphic function. Implementations that use maps or tries exploit that monomorphism in that they use a type like Map k v or Trie k v. Each map or trie is built around a particular (monomorphic) type of keys. That is, a single map or trie does not mix keys of different types.

Now I find myself wanting to memoize polymorphic functions, and I don’t know how to do it.

Continue reading ‘Memoizing polymorphic functions – part one’ »

A previous post described a data type of functional linear maps. As Andy Gill pointed out, we had a heck of a time trying to get good performance. This note describes a new representation that is very simple and much more efficient. It’s terribly obvious in retrospect but took me a good while to stumble onto.

The Haskell module described here is part of the vector-space library (version 0.5 or later) and requires ghc version 6.10 or better (for associated types).

Edits:

• 2008-11-09: Changed remarks about versions. The vector-space version 0.5 depends on ghc 6.10.
• 2008-10-21: Fixed the vector-space library link in the teaser.

Continue reading ‘Simpler, more efficient, functional linear maps’ »

The post Elegant memoization with functional memo tries showed a simple type of search tries and their use for functional memoization of functions. This post provides some composition tools for memo tries, whose definitions are inevitable, in that they are determined by the principle presented in Simplifying semantics with type class morphisms.

Continue reading ‘Composing memo tries’ »

Function memoization goes back at least as far as Donald Michie’s 1968 paper. The idea is to stash away results of a function call for reuse when a function is called more than once with the same argument. Given an argument, the memoized function looks up the argument in the internal memo table (often a hash table). If found, the previously computed result is reused. Otherwise, the function is applied, and the result is stored in the table, keyed by the argument. The table and its mutation are kept private from clients of the memo function.

Perhaps surprisingly, memoization can be implemented simply and purely functionally in a lazy functional language. Laziness allows the implementation to build the memo table once and for all, filling in all the results for the function at all domain values. Thanks to laziness, the values don’t actually get computed until they’re used. As usual with lazy data structures, once a component has been evaluated, future accesses come for free.

The implementation described in this post is based one I got from Spencer Janssen. It uses the essential idea of Ralf Hinze’s paper Generalizing Generalized Tries. The library is available on Hackage and a darcs repository. See the wiki page and hackage page for documentation and source code. I’ve compiled it successfully with ghc versions 6.8.2 through 6.10.3.

Edits:

• 2009-02-12: Fixed typo.
• 2009-11-14: Hackage page pointer.
• 2009-11-20: Fixed source code pointer.

Continue reading ‘Elegant memoization with functional memo tries’ »