16

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.

d12frosted
  • 1,280
  • 12
  • 33
  • 4
    Instead of just avoiding `undefined`, you could also use `foldl` to avoid potentially expensive operations. If your folding function exits early on a successful operation, then you can avoid performing expensive computations through laziness. There might be more clear ways to write it (monoids spring to mind), but folds can be nice for compiler optimizations. – bheklilr Sep 19 '14 at 20:54
  • Yes, I was thinking about this. But can't imagine a good example of such a function. – d12frosted Sep 19 '14 at 21:06

2 Answers2

13

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.

bheklilr
  • 53,530
  • 6
  • 107
  • 163
5

I can think of one (although it might be that this yields good code only with an optimizing compiler):

last = foldl (\_ x -> x) (error "emptyList")

It would not have the right behavior with foldl':

> foldl (\_ x -> x) (error "emptyList") [error "foo", "last"]
"last"
> foldl' (\_ x -> x) (error "emptyList") [error "foo", "last"]
"*** Exception: foo
Joachim Breitner
  • 25,395
  • 6
  • 78
  • 139