Non-Trivial Lazy Evaluation

by

  • Have you ever written an AI? Isn’t it annoying that you have to thread pruning information (e.g. maximum depth, the minimum cost of an adjacent branch, or other such information) through the tree traversal function? This means you have to write a new tree traversal every time you want to improve your AI. That’s dumb. With lazy evaluation, this is no longer a problem: write your tree traversal function once, to produce a huge (maybe even infinite!) game tree, and let your consumer decide how much of it to consume.

  • Writing a GUI that shows lots of information? Want it to run fast anyway? In other languages, you might have to write code that renders only the visible scenes. In Haskell, you can write code that renders the whole scene, and then later choose which pixels to observe. Similarly, rendering a complicated scene? Why not compute an infinite sequence of scenes at various detail levels, and pick the most appropriate one as the program runs?

  • You write an expensive function, and decide to memoize it for speed. In other languages, this requires building a data structure that tracks which inputs for the function you know the answer to, and updating the structure as you see new inputs. Remember to make it thread safe — if we really need speed, we need parallelism, too! In Haskell, you build an infinite data structure, with an entry for each possible input, and evaluate the parts of the data structure that correspond to the inputs you care about. Thread safety comes for free with purity.

  • Here’s one that’s perhaps a bit more prosaic than the previous ones. Have you ever found a time when && and || weren’t the only things you wanted to be short-circuiting? I sure have! For example, I love the <|> function for combining Maybe values: it takes the first one of its arguments that actually has a value. So Just 3 <|> Nothing = Just 3; Nothing <|> Just 7 = Just 7; and Nothing <|> Nothing = Nothing. Moreover, it’s short-circuiting: if it turns out that its first argument is a Just, it won’t bother doing the computation required to figure out what its second argument is.

    And <|> isn’t built in to the language; it’s tacked on by a library. That is: laziness allows you to write brand new short-circuiting forms. (Indeed, in Haskell, even the short-circuiting behavior of (&&) and (||) aren’t built-in compiler magic: they arise naturally from the semantics of the language plus their definitions in the standard libraries.)

In general, the common theme here is that you can separate the production of values from the determination of which values are interesting to look at. This makes things more composable, because the choice of what is interesting to look at need not be known by the producer.

More Related Contents:

  1. Does Haskell have tail-recursive optimization?
  2. How is this fibonacci-function memoized?
  3. Explain this chunk of haskell code that outputs a stream of primes
  4. What’s so bad about Lazy I/O?
  5. foldl versus foldr behavior with infinite lists
  6. What does the exclamation mark mean in a Haskell declaration?
  7. Why is lazy evaluation useful?
  8. Pseudo-quicksort time complexity
  9. Is Haskell’s mapM not lazy?
  10. `String’ is applied to too many type arguments
  11. How do I define Lisp’s apply in Haskell?
  12. Operating on a return from a Maybe that contains “Just”
  13. Is there a Haskell idiom for updating a nested data structure?
  14. Positive integer type
  15. Explicitly import instances
  16. How to compare two functions for equivalence, as in (λx.2*x) == (λx.x+x)?
  17. Why do 3 and x (which was assigned 3) have different inferred types in Haskell? [duplicate]
  18. How do I use fix, and how does it work?
  19. List of different types?
  20. What is Levity polymorphism
  21. How to infer the type of an expression manually
  22. Understanding the Haskell as-pattern
  23. Haskell: How to create most generic function possible that applies a function to tuple items
  24. Concrete example showing that monads are not closed under composition (with proof)?
  25. How to use (->) instances of Monad and confusion about (->)
  26. Composing function composition: How does (.).(.) work?
  27. Haskell GHC: what is the time complexity of a pattern match with N constructors?
  28. What’s the status of multicore programming in Haskell?
  29. Removing syntactic sugar: List comprehension in Haskell
  30. Can I match a data constructor wildcard in Haskell?

Leave a Comment