[Haskell-cafe] Order of evaluation
derek.a.elkins at gmail.com
Thu Jul 26 17:31:15 EDT 2007
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
More information about the Haskell-Cafe