Hackfoofery

Alson Kemp

Thinking About Haskell*: You Know Lazy Evaluation; You Just Don’t Know It

[Post updated to reflect comments. ...too much late night typing...] Lazy evaluation is a very novel aspect of Haskell. Turns out that it’s not that difficult to think about.

A very common example of lazy-ish evaluation is ‘&&’ operators used in lots of languages (using C#):

if ( (obj != null) && (obj.someMethod() == somethingElse) ) {
  // do something
}

obj.someMethod isn’t evaluated unless obj != null. So &&, a C# function/operator everyone knows and loves, is strict in its first parameter and lazy in its second. The previous code might act a little like the following:

if (obj != null){
  if (obj.someMethod() == somethingElse) ) {
    // do something
  }
}

If && were strict in both parameters, then it’d throw errors when the second parameter was unconditionally evaluated (e.g. null.someMethod()). If _&& weren’t lazy, it might act something like:

condition1 = (obj != null);
condition2 = (obj.someMethod() == somethingElse);
if (condition1 && condition2) {
    // do something
  }
}

Clearly, condition2 would throw an Exception when obj was null, so the if statement must not be evaluating the second parameter. It’s as if it were lazy…

Here’s the (slightly revised for clarity) definition of && from Haskell:

(&&)                    :: Bool -> Bool -> Bool
(&&) True x              =  x
(&&) False _             =  False

Just as with C#, the first parameter (x) must be evaluated, but the second parameter is only evaluated if the first parameter is True. && is strict in the first parameter and lazy in the second.

And That’s All There Is to Laziness?

Nope. It’s “turtles all the way down”.

Laziness is a defining feature of Haskell and a feature that separates Haskell from the vast majority of languages. Lazy evaluation isn’t confined to a few operators in Haskell; lazy evaluation starts at the first function/expression in your program and continues all the way down.

For more reading, check out here, here, here and here.

But I Don’t Want To Be Lazy

[Example fixed.] Then force evaluation of your parameters. How? One way is to use the $! function to force the evaluation of parameters.

f a b c = ((someFunction $! a) $! b) $! c

See here for more.


* These little bits have helped me think about Haskell. Maybe they’ll be useful for you, too.

Written by alson

December 16th, 2008 at 1:33 am

with 15 comments

15 Responses to 'Thinking About Haskell*: You Know Lazy Evaluation; You Just Don’t Know It'

Subscribe to comments with RSS or TrackBack to 'Thinking About Haskell*: You Know Lazy Evaluation; You Just Don’t Know It'.

  1. It’s only in Core that case expressions force evaluation. In ordinary Haskell, it doesn’t necessarily:

    [[code]]czo0MzpcImNhc2UgdW5kZWZpbmVkIG9mIF8gLSZndDsgNDIgIC0tIHlpZWxkcyA0MgpcIjt7WyYqJl19[[/code]]

    I think seq is the only way to force evaluation without knowing something about the type (and it really shouldn’t exist…).

    Luke Palmer

    16 Dec 08 at 3:59 am

  2. You aren’t quite correct about the final bit. case x only evaluates x as far as the pattern requires it, so a pattern of _ demands no evaluation. It is slightly more confusing because in GHC’s Core language case does evaluate one level, but it doesn’t work that way in Haskell even if you are using GHC – its just a detail for the implementers.

    If you do want to force evaluation, you need to use the seq function, which is a built in primitive.

    Neil Mitchell

    16 Dec 08 at 5:07 am

  3. Matching against “_” does not force evaluation in Haskell (see fig. 3(f) here: http://haskell.orgonlinereport/exps.html#case-semantics ). In the link you give, “len” and “acc” are evaluated using the “seq” operator (“len” would probably be anyway, since it is compared to 0).

    Asger C. Ipsen

    16 Dec 08 at 5:49 am

  4. You probably meant “But I Don’t Want To Be Lazy”

    Roman Cheplyaka

    16 Dec 08 at 5:59 am

  5. It might be helpful to mention more clearly that lazyness is not an all-or-nothing concept, rather, an expression/parameter may as well be partially evaluated.

    Andreas Krey

    16 Dec 08 at 6:21 am

  6. Your last example is wrong. A case that doesn’t use it’s result will not force the thunk being cased. Use bang patterns or deepSeq instead.

    Josef Svenningsson

    16 Dec 08 at 9:20 am

  7. Actually, using case like that doesn’t evaluate anything. The case expression evaluates exactly as much as it has to make sure the pattern matches. And since _ matches everything then nothing is evaluated. You need to use the (non-lambda-definable) seq function to evaluate arbitrary values.

    augustss

    16 Dec 08 at 9:44 am

  8. “if ( (obj != null) && (obj.someMethod() == somethingElse) ) {” This is not lazy evaluation, this is sequential and conditional execution.

    worthless

    16 Dec 08 at 10:05 am

  9. GHCi> case undefined of _ -> “test” “test”

    worthless

    16 Dec 08 at 10:06 am

  10. Roman, Argh! Fixed. – Alson

    alson

    16 Dec 08 at 12:42 pm

  11. Worthless,

    In terms of “Thinking about Haskell”, seeing ‘&&’ as lazy has helped me think about Haskell. Laziness can be pretty rough to grapple with and I thought that people would appreciate the ‘&&’ example as a lazy-ish thing they’ve used lots of time.

    Besides, I’m a little confused by your comment that ‘&&’ isn’t lazy. From the HaskellWiki:

    “Lazy evaluation causes that expressions are not evaluated when they are bound to variables, but their evaluation is deferred until their results are needed by other computations.”

    ‘&&’, whether in C# or Haskell, seems to fit that description.

    • Alson

    alson

    16 Dec 08 at 12:49 pm

  12. Luke, Josef, Asger,

    Agreed. That’ll teach me to put in code that I haven’t tested in ghci… Fixed.

    • Alson

    alson

    16 Dec 08 at 12:52 pm

  13. Andreas,

    I tried to make note of that, but didn’t do a great job. Adding more words…

    • Alson

    alson

    16 Dec 08 at 1:08 pm

  14. Just a note: $! is unfortunately not left associative, but right associative, so that last example won’t work, you have to write

    f a b c = ((g $! a) $! b) $! c

    (also, you had the f being recursive there, which probably wasn’t what you’d intended)

    I’d like to change $ and $! to be left associative like function application normally is for this, and a few other reasons.

    Cale

    16 Dec 08 at 11:25 pm

  15. Cale,

    “That’ll teach me to put in code I haven’t tested in ghci…” Take 2! Fixed.

    This little post just keeps on giving…

    • Alson

    alson

    17 Dec 08 at 1:49 am

Leave a Reply