Skip to content
master
Switch branches/tags
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
 
 
 
 
 
 
 
 
 
 

Talk: Elegant memoization

I gave this talk at the Hacker Dojo in Mountain View, California on April 3, 2014.

You can find the slides (PDF) in my talks folder.

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". 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, 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 of the idea, adapted from code by Spencer Janssen and using associated types.

About

A talk: "Elegant memoization"

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published