Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Practical use of `foldl`

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 and foldl'.

...

However, if the combining function is lazy in its first argument, foldl may happily return a result where foldl' 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.

like image 600
d12frosted Avatar asked Sep 19 '14 20:09

d12frosted


People also ask

What does foldl do?

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.

What is a fold in functional programming?

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 ...

How does Foldr work in Haskell?

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.

What is foldable Haskell?

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.


1 Answers

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.

like image 170
bheklilr Avatar answered Oct 24 '22 14:10

bheklilr