Today when I was working on one little script I used foldl
instead of foldl'
. I got stack overflow
, so I imported Data.List (foldl')
and was happy with this. And this is my default workflow with foldl
. Just use foldl'
when lazy version falls to evaluate.
Real World Haskell
says that we should use foldl'
instead of foldl
in most cases. Foldr Foldl Foldl' says that
Usually the choice is between
foldr
andfoldl'
....
However, if the combining function is lazy in its first argument,
foldl
may happily return a result wherefoldl'
hits an exception.
And a given example:
(?) :: Int -> Int -> Int
_ ? 0 = 0
x ? y = x*y
list :: [Int]
list = [2, 3, undefined, 5, 0]
okey = foldl (?) 1 list
boom = foldl' (?) 1 list
Well, I am sorry, but it's rather academic, interesting but academic example. So I am asking, is there any example of practical use of foldl
? I mean, when we can't replace foldl
with foldl'
.
P. S. I know, it's hard to define term practical
, but I hope you will understand what I mean.
P. P. S. I understand, why lazy foldl
is default in haskell. I don't ask anybody to move the mountain and make strict version as default. I am just really interested in examples of exclusive usage of foldl
function :)
P. P. P. S. Well, any interesting usage of foldl
is welcome.
With foldl , the function argument takes a default value, the first element of the list, and returns a new default value. When the list is empty, that default value will be the result of the fold.
In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order functions that analyze a recursive data structure and through use of a given combining operation, recombine the results of recursively processing its constituent parts, building up a ...
Haskell : foldr. Description: it takes the second argument and the last item of the list and applies the function, then it takes the penultimate item from the end and the result, and so on. See scanr for intermediate results.
Advanced Haskell The Foldable type class provides a generalisation of list folding ( foldr and friends) and operations derived from it to arbitrary data structures. Besides being extremely useful, Foldable is a great example of how monoids can help formulating good abstractions.
Here's a more practical example using the classic naive Fibonacci implementation to simulate an expensive computation:
fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
f :: Int -> Int -> Int
f a b = if b < 1000 then b else min b a
Then if you had
> -- Turn on statistics for illustrative purposes
> :set +s
> foldl f maxBound $ map fib [30, 20, 15]
987
(0.02 secs, 0 bytes)
> foldl' f maxBound $ map fib [30, 20, 15]
987
(4.54 secs, 409778880 bytes)
Here we have a drastic difference in runtime performance between the lazy and strict versions, with the lazy version winning out by a landslide. Your numbers may vary for your computer of course, but you'll definitely notice a difference in execution speed. The foldl'
forces each computation to occur, while foldl
does not. This can also be useful on something like
> foldl f maxBound $ map length [repeat 1, repeat 1, replicate 10 1]
10
Unlike the fib
example, this computation technically involves bottom since length $ repeat 1
will never finish its computation. By not having both arguments to f
be strict (as foldl'
does), we actually have a program that halts versus one that never will.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With