[Haskell-cafe] Order of evaluation

[Derek Elkins]

On Thu, 2007-07-26 at 12:04 -0500, Spencer Janssen wrote:
> 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.

To unsummarize, see http://www.haskell.org/haskellwiki/Stack_overflow