Characteristics

Scope: Local Safety: Best practice

Explanation

Memoization is the technique of caching previously calculated results with the intention of improving the speed of newer calculations.

Memoization is only possible with pure functions, but it is hard to implement with immutable data. But laziness make it easy, thus in Haskell it's preferable to exploit it as often as possible.

Any function with a countable domain can be mapped into a list comprehension... And now, I must ask your forgiveness for using the Fibonacci sequence calculation as an example, but we are already talking about algorithms, and that is the kind of problem where memoization gets applied to... So, let's get to the example.

This program runs in O(e^n) time and O(1) space:

  fib x
    | x <= 1 = 1
    | otherwise = fib (x - 1) + fib (x - 2)

Mapping it into a list comprehension, and exploiting laziness for memoization, the program now runs in O(n) time and O(n) space:

  fib x = fiblist ! x
    where
      fiblist = 1:1:[fiblist ! (x - 1) + fiblist ! (x - 2) | x <- [2..]]

Notice that lots of interesting problems have countable sets as domain. Here included graph traversals, string operations, and most of image processing. Non-countable sets don't really exist on computer programs, but some sets are dense enough that it makes sense to think about them as non-countable. The most obvious example are floating point numbers.

For non-countable domains, memoization already does usually not work that well, but is still possible. And it is still possible to exploit laziness for them in Haskell. But a useful implementation (when there is one) will vary a lot from case to case.

When Should I Use It?

As far as I can see, this is hands down the best way to get memoization in Haskell. Use it every time you want memoization.

If you have some interdependency over random elements, instead of the very ordered one on fib, you'll want to construct a map or an array out of that list. Just remember to get a lazy data structure.