CODEWITHSUNDEEP
haskellrecursiontail-recursion
RandomStudent
RandomStudent

Reputation: 427

Why is this tail-recursive Haskell function slower ?

I was trying to implement a Haskell function that takes as input an array of integers A and produces another array B = [A[0], A[0]+A[1], A[0]+A[1]+A[2] ,... ]. I know that scanl from Data.List can be used for this with the function (+). I wrote the second implementation (which performs faster) after seeing the source code of scanl. I want to know why the first implementation is slower compared to the second one, despite being tail-recursive?

-- This function works slow.
ps s x [] = x
ps s x y  = ps s' x' y'
            where
                s' = s + head y
                x' = x ++ [s']
                y' = tail y

-- This function works fast.
ps' s []   = []
ps' s y    = [s'] ++ (ps' s' y') 
             where 
                s' = s + head y
                y' = tail y

Some details about the above code:

Implementation 1 : It should be called as 

ps 0 [] a

where 'a' is your array.

Implementation 2: It should be called as

ps' 0 a

where 'a' is your array.

Upvotes: 3

Views: 444

Answers (2)

Manuel Eberl
Manuel Eberl

Reputation: 8278

I would like to mention that your function can be more easily expressed as 

drop 1 . scanl (+) 0

Usually, it is a good idea to use predefined combinators like scanl in favour of writing your own recursion schemes; it improves readability and makes it less likely that you needlessly squander performance.

However, in this case, both my scanl version and your original ps and ps' can sometimes lead to stack overflows due to lazy evaluation: Haskell does not necessarily immediately evaluate the additions (depends on strictness analysis).

One case where you can see this is if you do last (ps' 0 [1..100000000]). That leads to a stack overflow. You can solve that problem by forcing Haskell to evaluate the additions immediately, for instance by defining your own, strict scanl:

myscanl :: (b -> a -> b) -> b -> [a] -> [b]
myscanl f q []     = []
myscanl f q (x:xs) = q `seq` let q' = f q x in q' : myscanl f q' xs

ps' = myscanl (+) 0

Then, calling last (ps' [1..100000000]) works.

Upvotes: 1

lpsmith
lpsmith

Reputation: 707

You are changing the way that ++ associates. In your first function you are computing ((([a0] ++ [a1]) ++ [a2]) ++ ...) whereas in the second function you are computing [a0] ++ ([a1] ++ ([a2] ++ ..)). Appending a few elements to the start of the list is O(1), whereas appending a few elements to the end of a list is O(n) in the length of the list. This leads to a linear versus quadratic algorithm overall.

You can fix the first example by building the list up in reverse order, and then reversing again at the end, or by using something like dlist. However the second will still be better for most purposes. While tail calls do exist and can be important in Haskell, if you are familiar with a strict functional language like Scheme or ML your intuition about how and when to use them is completely wrong.

The second example is better, in large part, because it's incremental; it immediately starts returning data that the consumer might be interested in. If you just fixed the first example using the double-reverse or dlist tricks, your function will traverse the entire list before it returns anything at all.

Upvotes: 7

Related Questions