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