Meetup -- Elegant memoization

Conal Elliott will talk on "Elegant memoization", after which we will have time for lightning talks (5 minutes) as offered.

Abstract:

Functional programming languages emphasize the use of (pure) functions, but they also carry an implementation bias against them. In most functional programming languages, including Haskell, if you express a value and then access it twice, you’ll pay only once. For data structures, every component has this property. For functions, however, an analogous property does not hold: if you apply a function twice to the same argument, the result will be recomputed. Donald Michie invented a solution, which he called “memoization (https://en.wikipedia.org/wiki/Memoization)”. The trick is to store function results in a lookup table for later reuse. From this perspective, memoization is an imperative technique. Ironically, the technique is only correct for pure functions.

I’m going to talk about purely functional memoization. The idea, due to Ralf Hinze (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.3272), is to use a few simple type isomorphisms to guide and justify the memoization, leading to the systematic construction of trie data structures (“digital search trees”) from first principles. I'll show a Haskell implementation (http://hackage.haskell.org/package/MemoTrie) of the idea, adapted from code by Spencer Janssen and using associated types.