Haskell foldl c insufficient performance with (++)

Question

I have this code:

import Data.List newList_bad lst = foldl' (\acc x -> acc ++ [x*2]) [] lst newList_good lst = foldl' (\acc x -> x*2 : acc) [] lst 

These functions return lists with each element times 2:

 *Main> newList_bad [1..10] [2,4,6,8,10,12,14,16,18,20] *Main> newList_good [1..10] [20,18,16,14,12,10,8,6,4,2] 

In ghci:

 *Main> sum $ newList_bad [1..15000] 225015000 (5.24 secs, 4767099960 bytes) *Main> sum $ newList_good [1..15000] 225015000 (0.03 secs, 3190716 bytes) 

Why is the newList_bad function 200 times slower than newList_good ? I understand that this is not a good solution for this task. But why is this innocent code so slow?

What is this "4767099960 bytes"? For this simple operation, Haskell used 4 GiB ??

After compilation:

 C:\1>ghc -O --make test.hs C:\1>test.exe 225015000 Time for sum (newList_bad [1..15000]) is 4.445889s 225015000 Time for sum (newList_good [1..15000]) is 0.0025005s 

Answer 1

Classic list behavior.

Recall:

 (:) -- O(1) complexity (++) -- O(n) complexity 

So you create O (n ^ 2) algo instead of O (n).

For this common case of adding lists gradually, try using dlist or just undo at the end.

Answer 2

There is a lot of confusion about this problem. The usual reason is that "adding repeatedly at the end of the list requires repeated crawls of the list and thus O(n^2) ." But that would be so easy with a rigorous assessment. With a lazy evaluation, everything should be postponed, so he asks whether there really are these repeated crawls and additions. The addition at the end is triggered by consumption in front, and since we consume in front, the list becomes shorter, so the exact time of these actions is unclear. Thus, the real answer is more subtle and concerns the specific steps of reduction with a lazy assessment.

The immediate culprit is that foldl' only leads to the fact that his argument of the battery goes into the normal form of a weak head, i.e. until a lax constructor is shown. The functions involved here

 (a:b)++c = a:(b++c) -- does nothing with 'b', only pulls 'a' up []++c = c -- so '++' only forces 1st elt from its left arg foldl' fz [] = z foldl' fz (x:xs) = let w=fzx in w `seq` foldl' fw xs sum xs = sum_ xs 0 -- forces elts fom its arg one by one sum_ [] a = a sum_ (x:xs) a = sum_ xs (a+x) 

and therefore the actual recovery sequence (with g = foldl' f )

 sum $ foldl' (\acc x-> acc++[x^2]) [] [a,b,c,d,e] sum $ g [] [a,b,c,d,e] g [a^2] [b,c,d,e] g (a^2:([]++[b^2])) [c,d,e] g (a^2:(([]++[b^2])++[c^2])) [d,e] g (a^2:((([]++[b^2])++[c^2])++[d^2])) [e] g (a^2:(((([]++[b^2])++[c^2])++[d^2])++[e^2])) [] sum $ (a^2:(((([]++[b^2])++[c^2])++[d^2])++[e^2])) 

Please note that we have only completed steps O(n) . a^2 immediately available for consumption sum , but b^2 is not. We stay here with a left nested ++ expression structure. The rest is best explained in this answer by Daniel Fisher . Its essence is that in order to get b^2 out you need to follow steps O(n-1) - and the structure remaining after this access will still remain nested, so the next access will take steps O(n-2) , and t .d. is the classical behavior of O(n^2) . Thus, the real reason is that ++ does not force or rebuild its arguments in order to be effective .

This is actually contrary to intuition. We could expect a lazy appraisal to magically “do this” for us here. In the end, we only express our intention to add [x^2] to the end of the list in the future, we actually do not do it right away. Thus, the time is turned off here, but it can be done correctly - when we go to the list, new elements will be added to it and will be destroyed immediately if the time was correct: if c^2 will be added to the list after b^2 (by -differently), say, before (in time) b^2 will be consumed, bypass / access will always be O(1) .

This is achieved using the so-called "difference list" method:

 newlist_dl lst = foldl' (\z x-> (z . (x^2 :)) ) id lst 

which, if you think about it for a moment, looks exactly like your version ++[x^2] . It expresses the same intention and leaves the left nested structure too.

The difference, as explained in the same answer by Daniel Fisher, is that a (.) Chain , when it is forcibly forced, rebuilds itself in the structure of the nested right ($) / strong> ¹ in O(n) , after which each access is equal to O(1) , and the addition time will be optimal, as described in the previous paragraph, so we remain with the general O(n) behavior.

---

¹ which is kind of magical, but it happens. :)

Answer 3

In addition to other answers with a bigger perspective: with lazy lists, using foldl' in a function that returns a list is usually a bad idea. foldl' often useful when you reduce a list to a strict (non-fuzzy) scalar value (for example, by summing a list). But when you build a list as a result, foldr usually better, because of laziness; constructor : lazy, so the tail of the list is not computed until it is needed.

In your case:

 newList_foldr lst = foldr (\x acc -> x*2 : acc) [] lst 

This is actually the same as map (*2) :

 newList_foldr lst = map (*2) lst map f lst = foldr (\x acc -> fx : acc) [] lst 

Assessment (using the first map -less definition):

 newList_foldr [1..10] = foldr (\x acc -> x*2 : acc) [] [1..10] = foldr (\x acc -> x*2 : acc) [] (1:[2..10]) = 1*2 : foldr (\x rest -> fx : acc) [] [2..10] 

This is something like Haskell will evaluate when newList [1..10] forced. He evaluates only further if the consumer requires this result, and only as much as necessary to satisfy the consumer. For example:

 firstElem [] = Nothing firstElem (x:_) = Just x firstElem (newList_foldr [1..10]) -- firstElem only needs to evaluate newList [1..10] enough to determine -- which of its subcases applies—empty list or pair. = firstElem (foldr (\x acc -> x*2 : acc) [] [1..10]) = firstElem (foldr (\x acc -> x*2 : acc) [] (1:[2..10])) = firstElem (1*2 : foldr (\x rest -> fx : acc) [] [2..10]) -- firstElem doesn't need the tail, so it never computed! = Just (1*2) 

It also means that newList based on newList can work with infinite lists:

 newList_foldr [1..] = [2,4..] firstElem (newList_foldr [1..]) = 2 

If you use foldl' , on the other hand, you should always evaluate all lists, which also means that you cannot work with infinite lists:

 firstElem (newList_good [1..]) -- doesn't terminate firstElem (newList_good [1..10]) = firstElem (foldl' (\acc x -> x*2 : acc) [] [1..10]) = firstElem (foldl' (\acc x -> x*2 : acc) [] (1:[2..10])) = firstElem (foldl' (\acc x -> x*2 : acc) [2] [2..10]) -- we can't short circuit here because the [2] is "inside" the foldl', so -- firstElem can't see it = firstElem (foldl' (\acc x -> x*2 : acc) [2] (2:[3..10])) = firstElem (foldl' (\acc x -> x*2 : acc) [4,2] [3..10]) ... = firstElem (foldl' (\acc x -> x*2 : acc) [18,16,14,12,10,8,6,4,2] (10:[])) = firstElem (foldl' (\acc x -> x*2 : acc) [20,18,16,14,12,10,8,6,4,2] []) = firstElem [20,18,16,14,12,10,8,6,4,2] = firstElem (20:[18,16,14,12,10,8,6,4,2]) = Just 20 

The foldr based algorithm performed 4 steps to compute firstElem_foldr (newList [1..10]) , while about 21 steps were taken on the basis of foldl' . Worse, 4 steps are a constant value, while 21 is proportional to the length of the input list - firstElem (newList_good [1..150000]) takes 300 001 steps, and firstElem (newList_foldr [1..150000] takes 5 steps, like firstElem (newList_foldr [1..] , for that matter.

Note that firstElem (newList_foldr [1.10]) works in constant space as well as in constant time (it should: you need more than constant time to allocate more than constant space). The truism from strict languages ​​- " foldl is tail recursive and works in constant space, foldr not tail recursive and works in linear space or worse" - is not true in Haskell.