What's the meaning of strict version in haskell?

Question

Follow <Real World Haskell> , it is said foldl' are strict version of foldl.

But it's hard for me to understand , what does strict mean??

foldl f z0 xs0 = lgo z0 xs0
         where
            lgo z []     =  z
            lgo z (x:xs) = lgo (f z x) xs


foldl' f z0 xs0 = lgo z0 xs0
    where lgo z []     = z
          lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs

Lusty

Compare the source code for the two versions of foldl, and you might be enlightened. – Lama

@Lama maybe, can you answer this? – Lusty

As you can see, foldl' computes the first argument to lgo before the call, whereas foldl will (in general) pass a thunk that will get evaluated when needed. – Lama

possible duplicate of Haskell - strict vs non-strict with foldl – Boo

Answer 1

foldl and (the strict) foldl' are close to semantically equivalent. The difference is in performance, especially when you are transversing a large list. The laziness has an overhead of building a thunk and foldl' is the more efficient way to arrive at that result because it doesn't build a huge thunk.

There is a really good article explaining this in detail on Haskell Wiki

Strict functions works like functions in C or other languages in that their arguments are generally eagerly evaluated.

Cloven

Answer 2

It is not widely known, but foldl' is actually non-strict in its accumulator argument! Recall the type:

foldl' :: (a -> b -> a) -> a -> [b] -> a

Its strictness in argument 2 depends on the strictness of the function given for argument 1, as you see if you pass const:

Prelude Data.List> foldl' (const (+1)) undefined [1]
2
Prelude Data.List> foldl' (const (+1)) undefined [1..4]
5

You would have thought, naively, that "foldl' is strict" means "strict in the accumulator argument". The above contradicts that.

However, it is even more insidious, as the strictness is only on the result of the function application in the cons case of the loop. So you still get bottoms if you enter the base case, but not the inductive case:

Prelude Data.List> foldl' (const (+1)) undefined []
*** Exception: Prelude.undefined

So the strictness in argument 2 also depends on the value of argument 3!

This is how I'd write it: "fully" strict in its 2nd argument.

foldl' f z0 xs0 = go z0 xs0
  where
    go !z []     = z
    go !z (x:xs) = go (f z x) xs

Which is truly strict in its second argument, as you can see :

Prelude Data.List.Stream> foldl' (\a b -> 1) undefined [undefined]
*** Exception: Prelude.undefined

Compared with the Haskell2010 version:

Prelude Data.List.Stream> Data.List.foldl' (\a b -> 1 ) undefined [undefined]
1

This actuall has a practical impact -- the current definition will not unbox its accumulator argument consistently.

Historical note: this was discovered when we were specifying the list library's strictness semantics for the stream fusion paper in 2007, and the approach to specifying strictness is given in Duncan Coutt's PhD thesis.

Foushee

Answer 3

A strict function is a function whose arguments are evaluated before the body is.

Grison

No, it's not a function whose arguments are evaluated before the call. A strict function is, informally, a function which evaluates its arguments. – Lama

Tinctorius, what do you mean? – Lama

Formally, a function is strict in an argument if it returns bottom when that argument is bottom. This means a function can be strict, in the formal sense, without evaluating the argument. This might sound like splitting hairs, but it's important when doing strictness analysis. – Lama

@Lama That's not what's meant in this context though, is it? foldl evaluates to bottom in the same cases that foldl' does - it just does so later, no? – Grison

@sepp2k: No. For example: foldl (\x y -> y) (error "empty") [1,undefined,2] is 2, but the same expression with foldl' is ⊥. – Gula