Strictness
Jay Cox
sqrtofone@yahoo.com
Fri, 15 Mar 2002 20:16:49 -0600 (CST)
Alright. I know the haskell community probably gets tired of my long
winded posts. I This post probably shouldn't even be on
haskell@haskell.org (more like on haskell-cafe). I also realize that
these posts may not mean much to you; many of you may have figured out
most of this strictness business long, long ago and you are long bored of
me.
But I do feel strictness misconceptions and such are a potentially big
problem with using haskell. I even at one time decided haskell might not
be worth learning (more) about because it seemed like it might be too hard
to analyze memory usesage and the like to create efficient programs.
I think I may eventually attempt to write a haskell lazyness/strictness
FAQ. I feel a bit underqualified for the job, so I'm probably going to
need help in verification of what I may say in it. If anything, I hope
for some help so that i will not embarass the haskell community!
Or, at the very least, I may eventially add something to the haskell wiki.
I'm not sure which.
Any critique is welcome.
On Fri, 15 Mar 2002, Ronny Wichers Schreur wrote:
> matt hellige writes (to the haskell mailing list):
>
> >[..] consider:
> > sum 0 x = x
> > sum x y = x + y
> >
> >if the first argument is 0, we don't need to inspect the second
> >argument at all.
>
> But sum returns its second argument, so it's still strict in that
> argument.
Oh boy. You are right. sum 0 _|_ = _|_, since obviously x = x. but what
about sum x _|_? assuming (+) for integers, (+) is strict on both
arguments. thus
sum x _|_ = x + _|_ = _|_
Thus that definition of sum is strict on both arguments. (Apologies
to Matt Hellige for incorrect analysis in private message).
That also means my sumpeano isn't just strict on the second argument.
data Peano = Zero | Succ (Peano)
sumpeano blah (Succ x) = sumpeano (Succ blah) x
sumpeano blah Zero = blah
If the initial second argument of sumpeano is Zero, then sumpeano IS
strict on the second argument, by the same reasoning above.
But if it is not, then sumpeano _|_ (Succ x) = sumpeano
(Succ _|_) x. When sumpeano finally reaches Zero in the second
argument (for a initial non-Zero argument) the result will be a
cascade of Succ applications like (Succ.) (Succ.) (Succ.) (Succ.)
_|_
which, well, is not equivalent to _|_ (nor will it be unless all
applications have been forced.. Therefore sumpeano is,
CONDITIONALLY strict in the first argument!
(The reader may wonder why I chose the "(Succ.)" notation. I wanted to
give pause to the fact that sumpeano is generating Succ "thunks" which
will generate Succ (Succ (Succ ...))) etc, and not the actual structure.
perhaps I'm trying to be overly accurate for this argument.)
In all the literature I've read (which, by the way, is not much) I've
never seen such a phrase as conditionaly strict or conditionally lazy.
Is such a conseption as being conditionally strict or conditionally lazy
fairly useful? Or is this where the phrase "non-strict" comes in?
Hmmm, redefining sumpeano in terms of functions of 1 argument, (and
switching around the arguments around for the sake of argument) May also
give some insight. Either (sumpeano z) is a strict function, or, it
isn't.
sumpeano' Zero = id -- id _|_ = _|_
sumpeano' (Succ x) = \blah -> (sumpeano' x) (Succ blah)
Yet of course there are functions in common use which one could say have
arguments which are fully lazy. take the definiton of map.
map f [] = []
map f (x:xs) = f x : map f xs
f can be bottom easily. take length $ map _|_ [1..5] for example. (for
your pretend bottom, you could use error, as in bottom = error "I'm _|_!")
This is quite intriguing. I've learned something today. I hope my post
proves usefull to somebody else.
> Cheers,
>
> Ronny Wichers Schreur
Thanks,
Jay Cox