[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
    ^^     http://qrnik.knm.org.pl/~qrczak/

More information about the Haskell-Cafe mailing list