# Lazy Memoization

## 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.