[Haskell-cafe] Some random newbie questions
Marcin 'Qrczak' Kowalczyk
qrczak at knm.org.pl
Sun Jan 9 14:52:46 EST 2005
Jorge Adriano Aires <jadrian at mat.uc.pt> writes:
>> Naive use of foldl. I tend to think the default foldl should be
>> strict (ie. replaced by foldl') -- are there important cases where it
>> needs to be lazy?
> One simple example would be,
>> reverse = foldl (flip (:)) 
No, it would work with strict foldl too. In fact in the absence
of optimization it would work better (uses less time and space).
The optimization required is inlining and strictness analysis.
A function which requires lazy foldl for correctness would have
to be sometimes lazy in its first argument, and at the same time
some partial results would have to be undefined. By "function"
I mean the first argument of foldl, treated as a binary function.
Here this doesn't apply because flip (:) x y is always defined. And
another common case for foldl, sum, doesn't apply because (+) is
usually strict on both arguments (although in principle it does not
have to be true because of overloading, which implies that a compiler
can only optimize particular specializations of sum, not generic sum).
I don't know of any real-life example.
Perhaps there are cases where evaluating partial results is correct
but inefficient. I don't know such case either.
__("< Marcin Kowalczyk
\__/ qrczak at knm.org.pl
More information about the Haskell-Cafe