role of seq, $!, and bangpatterns illuminated with lazy versus strict folds Re: [Haskell-cafe] What is the role of $!?

Albert Y. C. Lai trebla at
Mon Dec 10 20:43:28 EST 2007

Thomas Hartman wrote:
> -- (myfoldl f q ) is a curried function that takes a list
> -- If I understand currectly, in this "lazy" fold, this curried function 
> isn't applied immediately, because
> -- by default the value of q is still a thunk
> myfoldl f z [] = z
> myfoldl f z (x:xs) = ( myfoldl f q  ) xs
>   where q = z `f` x

Sorry to say "this curried function isn't applied immediately" is wrong. 
The curried function is applied immediately. This is independent of what 
happens to q. q remains a thunk. myfoldl f q xs moves on immediately. 
Next iteration's z is this iteration's q, and remains a thunk too.

It is also noteworthy that

   a b c d
= (a b c) d
= ((a b) c) d

They are syntactic sugar of each other.

> -- here, because of the definition of seq, the curried function 
> (myfoldl' f q) is applied immediately
> -- because the value of q is known already, so (myfoldl' f q ) is WHNF
> myfoldl' f z [] = z
> myfoldl' f z (x:xs) = seq q ( myfoldl' f q ) xs
>   where q = z `f` x

The seq causes q to become WHNF. This is independent of what happens to 
(myfoldl' f q).

In general in many compilers seq x y digresses to reduce x to WHNF, then 
"we now return you to the scheduled programming of whatever should 
happen to y".

> --same as myfoldl'
> myfoldl'' f z [] = z
> myfoldl'' f !z (x:xs) = ( myfoldl'' f q ) xs
>   where q = z `f` x

This is not the same as myfoldl'. This does not reduce q to WHNF - not 
now. Instead, z is reduced to WHNF now. As for q, this iteration's q 
becomes the next iteration's z, so this iteration's q will become WHNF 
next iteration.

It is unusual to observe any difference because usually one experiments 
with number crunching only, where no one cares whether evaluation is one 
iteration early or late. However, this operator will show the difference.

mydisj _ True = True
mydisj True False = True
mydisj False False = False

myfoldl' mydisj (error "bottom") [True]  --> True
myfoldl'' mydisj (error "bottom") [True] --> exception: bottom

> myfoldl''' f z [] = z
> myfoldl''' f z (x:xs) = (myfoldl''' f $! q) xs
>   where q = z `f` x

This is the same as myfold'.

myfold' and myfold''' are the same as what's on the wiki.

More information about the Haskell-Cafe mailing list