Memoization of problem

puzzle.lhs

Michaels solution
=================

> a 0 y = 1
> a x 0 = 1
> a x y = a (x-1) y + a x (y-1)

> result = map (\x -> a x x) [0..]

Memoised form
=============

Lazy memoisation is where you refactor the definition to make use of 
a table storing the results you have previously calculated.

Let us define a table (a list of lists) that has all the x & y values 
of some Haskell function, `paths`.

> pathsTbl = [ [ paths' x y
>              | y <- [0..] ]
>            | x <- [0..] ]

If we want an interface like `a` we can define a function that looks 
up the value for a paticular x and y. Due to Haskell's laziness, once 
a particular x & y have been looked up, it will remember the result 
for as long as it has memory to do so.

> paths x y = pathsTbl !! x !! y

Now let us adjust the definition of `a` such that it uses the table 
where results have already been cacluated.

> paths' 0 y = 1
> paths' x 0 = 1
> paths' x y = paths (x-1) y + paths x (y-1)

And tada!

> memoresult = map (\x -> paths x x) [0..]

For example, can now calculate `memoresult !! 100` pretty quickly.