[Haskell-cafe] Order of evaluation

[Spencer Janssen]

On Thursday 26 July 2007 11:02:00 Jon Harrop wrote:
> On Thursday 26 July 2007 17:03:31 C.M.Brown wrote:
> > Hi Jon,
> >
> > On Thu, 26 Jul 2007, Jon Harrop wrote:
> > > If you have a boolean-or expression:
> > >
> > >   a || b
> > >
> > > will "a" be evaluated before "b" in Haskell as it is in other
> > > languages?
> >
> > Yes, I believe it is defined thus:
> >
> > True || _    = True
> > _    || True = True
> > _    || _    = False
> >
> > Therefore it is strict in its first argument (it needs to evaluate its
> > first argument in order to know which pattern match to take).
>
> Wonderful, thanks guys. The reason I ask is that I'm just looking over the
> Haskell ray tracer and it occurred to me that evaluation order makes an
> asymptotic difference to performance. The reason is simply that one order
> considers near spheres first and culls far spheres whereas the opposite
> order ends up traversing all spheres.
>
> Do foldl and foldr reduce from the first and last elements of a list,
> respectively?

Well, beginning and end are somewhat fuzzy concepts when laziness is involved.  
Consider this example:

 foldr (||) False [a, b, c] === (a || (b || (c || False)))
 foldl (||) False [a, b, c] === (((False || a) || b) || c)

Note that the least-nested application with foldr is (a || ...) -- this means 
that foldr can potentially yield some result after looking at the first 
element of the input.  This is especially useful with (||), because it only 
uses the second argument when the first is False.

In contrast, foldl's least-nested application is (... || c) -- foldl must 
traverse to the end of the input before giving an answer.  As it is traveling 
to the end, it will also build up the expression seen in the example.  On the 
surface, it seems we'll require O(n) heap to build this thunk.  However, if 
the compiler is sufficiently smart, bits of this expression will be evaluated 
as you go along, requiring only O(1) memory, rather than O(n).  We can also 
force this incremental evaluation with Data.List.foldl'.

Now, imagine folding (+) instead of (||).  (+) evaluates both arguments before 
computing a result.  In that case, foldr will take O(n) stack.  With a 
sufficiently smart compiler, foldl will only use O(1) memory.

To summarize:
 Use foldr when the operator is lazy (||, &&, ++, :).
 Use foldl when the operator is strict (*, +).
 Use foldl' when you don't trust the compiler to optimize foldl.

> Specifically, I'm wondering if this has an effect on the foldr optimization
> that Spencer proposed (that certainly gives a ~50% speedup here) that was
> attributed to avoiding lazy accumulators, IIRC.

Did I propose something?  I recall looking at this code before, but I can't 
remember the details.


Cheers,
Spencer Janssen