Why does this simple O (n) Haskell algorithm behave like O (2 ^ n)?

Question

Haskell caches the results of pure function calls, which is one of many reasons for the separation between pure and unclean behavior. However, this function, which should work in O (n), where n is less than 50 , works very slowly:

 lucas 1 = 1 lucas 2 = 3 lucas n = lucas (n-1) + lucas (n-2) map (lucas) [1..50] 

The first thirty terms or so are calculated together in a second, then 31 takes half a second or so, 32 takes a full second, 33 takes a few seconds, 34 takes 6 seconds, 35 takes 11 seconds, 36 takes 17 seconds ...

Why is this feature so slow? If the GHC interactive runtime is caching, each lucas call should only include a summation of the two previous cached terms. One additional operation to search for term 3, one additional addition to searching for term 4, one additional addition to searching for term 5, so term 50 is achieved only with a total of 48 caching related additions. A function shouldn't take a second about a second to find at least the first few thousand terms, why is performance so terrible?

I waited more than half an hour for the lucas 500 to calculate.

Answer 1

The reason your version is very slow is because there are no notes for the parts lucas (n-1) and lucas (n-2) - so both values ​​will be recalculated (recursively) again and again, which is very slow.

The solution is to save the calculated values ​​somewhere:

using list-lazyness

Here is a simple version that will do the same as your code snippet, but should be faster - it will save the already calculated parts in the list itself:

 lucasNumbers :: [Integer] lucasNumbers = 1:3:zipWith (+) lucasNumbers (tail lucasNumbers) first50 :: [Integer] first50 = take 50 lucasNumbers 

the reason this happens faster is because now the laziness of the list will help you remember the different parts

You can learn a lot about this if you are looking for Fibonacci sequences in Haskell (this is really the same as yours;))

using unfoldr

another (possibly less magical) way to do this is with Data.List.unfoldr - here the already calculated parts (or those that matter - the last and second-last elements) will be in the state that you pass for the expand operation:

 lucasNumbers :: [Integer] lucasNumbers = unfoldr (\ (n,n') -> Just (n, (n',n+n'))) (1,3) 

---

to your comment / question:

Assuming you are talking about x(n) = x(n-1)^2-2 , you can do it like this:

 lucasLehmer :: [Integer] lucasLehmer = 4 : map (\ x -> x^2-2) lucasLehmer 

which will give something like this:

 λ> take 5 lucasLehmer [4,14,194,37634,1416317954] 

Maybe you should try the unfoldr version.