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

Answer 1

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.

Answer 2

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.

Answer 3

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