Order of evaluation
If you have a boolean-or expression: a || b will "a" be evaluated before "b" in Haskell as it is in other languages? -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
On Thursday 26 July 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. The definition of (||) is roughly True || b = True False || b = b Which de-sugars to (||) = \ a b -> case a of True -> True False -> b Which does exactly what you want. Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs
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). Chris.
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? 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. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
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
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
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, although the meaning of the phrase "evaluated before" is a bit tricky in a lazy language, so it's probably better to state it with denotational semantics alone: _|_ || b = _|_ Maybe you also want to know whether the second argument "is evaluated". This is answered by True || _|_ = True False || _|_ = _|_ Regards, apfelmus
participants (6)
-
apfelmus -
C.M.Brown -
Derek Elkins -
Jon Harrop -
Jonathan Cast -
Spencer Janssen