[Haskell-cafe] Some random newbie questions
Marcin 'Qrczak' Kowalczyk
qrczak at knm.org.pl
Sun Jan 9 16:30:03 EST 2005
Jorge Adriano Aires <jadrian at mat.uc.pt> writes:
>> 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.
> Is this also true if your just going to use the first few elements after
> reversing it?
Yes. A strict fold would evaluate cons cells of the result while they
are constructed, not list elements. They are all defined (flip (:) x y
is always defined), so a strict foldl is correct.
Making a cons cell should be not more expensive than making a thunk
which will make a cons cell when evaluated. Well, unless the
implementation doesn't inline flip and thus making these thunks
is actually faster than running them. In this case a lazy foldl is
more efficient than a strict foldl, as long as a sufficiently small
part of the result is used; it's always less efficient if the whole
result is examined.
__("< Marcin Kowalczyk
\__/ qrczak at knm.org.pl
More information about the Haskell-Cafe