Effective Haskell

Memoizing editDistance

We’ve narrowed down our immediate performance problem to recalculating the same edit distances many times. The question now is, what can we do about that? One option is to simply avoid recalculating distances that we’ve already calculated once. If we replace our editDistance function with a version that remembers arguments it’s been called with, and the results that were returned, then we can use the cached values rather than recomputing the distance whenever we encounter a familiar pair of strings. This is a technique called memoization, and it’s common in many different languages and styles of programming.

When we want to memoize a function, Haskell offers us both some benefits and some challenges. The most immediate ...