optimizing recursive function performance (euler 15: lattice paths)

Question

I'm trying to solve project eulers 15th problem, lattice paths (http://projecteuler.net/problem=15).

My first attempt was to solve the problem line by line and then taking the last element in the last line.

number_of_ways_new_line last_line = foldl calculate_values [] last_line
                                    where
                                      calculate_values lst x = lst ++ [(if length lst > 0 then (last lst) + x else head last_line)]

count_ways x = foldl (\ lst _ -> number_of_ways_new_line lst) (take x [1,1..]) [1..x-1]

result_15 = last $ count_ways 21

This works and is fast, but I think it is really ugly. So I thought about it for a while and came up with a more idiomatic function (please correct me if I get this wrong), that sovles the problem using recursion:

lattice :: Int -> Int -> Int
lattice 0 0 = 1
lattice x 0 = lattice (x-1) 0
lattice 0 y = lattice (y-1) 0
lattice x y
  | x >= y    = (lattice (x-1) y) + (lattice x (y-1))
  | otherwise = (lattice y (x-1)) + (lattice (y-1) x)

This works good for short numbers, but it doesn't scale at all. I optimized it a little bit by using the fact that lattice 1 2 and lattice 2 1 will always be the same. Why is this so slow? Isn't Haskell memoizing previous results, so that whenever lattice 2 1 is called it remembers the old result?

Answer 1

Now this problem can be solved mathematically be manipulating the recurrence relations into a closed form, but I'll focus on the more interesting problem, memoizing.

First we can use Data.Array (this is the lazy one)

 import Data.Array as A

 lattice x y = array ((0, 0), (x, y)) m ! (x, y)
   where m = [(,) (x, y) (lattice' x y) | x <- [0..x], y <- [0..y]
         lattice' 0 0  = 1
         lattice' x 0 = lattice (x-1) 0
         lattice' 0 y = lattice (y-1) 0
         lattice' x y | x >= y    = (lattice (x-1) y) + (lattice x (y-1))
                      | otherwise = (lattice y (x-1)) + (lattice (y-1) x)

Now these recurrences go through the map, but, since the map is lazy, once a map entry is evaluated, it's thunk will be mutated to be a simple value ensuring it's only ever computed once.

We can also use the wonderful memo-combinators library.

 import Data.MemoCombinators as M
 lattice = memo2 M.integral M.integral lattice'
   where lattice' 0 0 = 1
         lattice' x 0 = lattice (x-1) 0
         lattice' 0 y = lattice (y-1) 0
         lattice' x y | x >= y    = lattice (x-1) y + lattice x (y-1)
                      | otherwise = lattice y (x-1) + lattice (y-1) x

Answer 2

This answer is indeed slow, because it depends on multiple recursions at the same time.

Let's examine the lattice function. What does it do? It returns either the sum of two latticefunctions, another lattice function, or the number one.

Now let's run down an example: lattice 2 2.
This equals lattice 1 2 + lattice 2 1.
This equals lattice 0 2 + lattice 1 1 + lattice 1 1 + lattice 2 0.
This equals ...

Do you realize the problem? There is not a single case of multiplication or adding a constant in your code. This means that the entire function will boil down to:

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + ... + 1

This sum is your final result. However, every 1 in the above sum is the result of one or multiple function calls. So your function will be evaluated more often than the result is worth.

Now consider that lattice 20 20 yields about 150 billion (it's an estimate, so I don't spoil too much).

This means your function gets evaluated around 150 000 000 000 times.

Yikes.

Don't feel bad for this mistake. I once said:

fibbonaci x = fibbonaci (x-1) + fibbonaci (x-2)

I encourage you to figure out why this is such a bad idea.

PS be glad they didn't ask for lattice 40 40. That would've taken more than 10^23 function calls, or at least 3 million years.

PPS your acceleration by calculating only one side will only slow down execution, as the amount of function calls doesn't decrease, however the time per function call will.

disclaimer: This is the first piece of Haskell code I've ever seen.