© Stefania Loredana Nita and Marius Mihailescu 2019
Stefania Loredana Nita and Marius MihailescuHaskell Quick Syntax Referencehttps://doi.org/10.1007/978-1-4842-4507-1_21

21. Lazy Evaluation

Stefania Loredana Nita1  and Marius Mihailescu1
(1)
Bucharest, Romania
 

You already know that Haskell is based on lazy evaluation. This means that the expressions are evaluated only when it is necessary. But what is “necessary”? In this chapter, you will get an answer to that question, and you will take a deeper look at lazy evaluation in Haskell.

First, let’s take a look at strict evaluation, which is the opposite of lazy evaluation. Suppose you have this function:
f x y = 2*y

If you call f (1234^100) 3, in strict evaluation the first argument will be evaluated and then the second one. Looking closely at the function body, you can see that the first argument is not used. Still, it is evaluated in a strict evaluation approach, which is useless in this particular example. The advantage of strict evaluation is that it knows for sure when and in what order things will happen. For example, if you write f(count_apples(), sing_song()) in Java, first count_apples() is evaluated, and then sing_song() is evaluated. Finally, their results are passed to f, which will be evaluated. When the results are not used in the body of f, extra work is done.

Languages are also focused on side effects. A side effect is any event that triggers the evaluation of an expression to interact with something outside itself. Lazy evaluation does not know when a certain expression will be evaluated, so a side effect would be useless. But a pure programming language would not make too many things; it is restrictive.

In Haskell, side effects are handled in an elegant manner, through the IO monad, where they are restricted so that they do not affect the essential purity of the language.

As you saw at the beginning of the chapter, lazy evaluation means that the evaluation of an expression is postponed as much as possible; it’s evaluated in the moment when it really is needed and only as far as needed, not further. The arguments of a function are just packed as unevaluated expressions called thunks , without doing any computation. In the example f (1234^100) 3, the arguments are packed, and the function is called immediately. As (1234^100) is not used, it remains a thunk, and no additional work is done. In other words, the expressions are evaluated when they pattern match.

Here’s a simple example:
Prelude> pick a b c = if a > c then a else b
Prelude> pick (7+2) (9+1) (3+2)
9
In strict evaluation, this would be resolved as follows:
pick (7+2) (9+1) (3+2)
pick 9 (9+1) (3+2)
pick 9 10 (3+2)
pick 9 10 5
if 9 > 5 then 9 else 10
if True then 9 else 10
9
With lazy evaluation, it is resolved, beginning with the outermost expression.
pick (7+2) (9+1) (3+2)
if (7+2) > (3+2) then (7+2) else (9+1)
if 9 > (3+2) then 9 else (9+1)
if 9 > 5 then 9 else (9+1)
if True then 9 else (9+1)
9
What are the advantages of lazy evaluation? There are many, described here:
  • Lazy languages are pure, which means it is difficult to identify side effects. Function reasoning is done using equality, for example, fct y = y + 5.

  • In lazy languages, “value restriction” is not needed, which means that the syntax is cleaner. For example, in nonlazy languages you can use keywords like var or function to define things, but in Haskell, all these things fall into one area. Lazy languages permit you to write code in a “very functional” manner, which enables a top-down approach to coding. This feature has the advantage that things can be understood in fragments. For example, in Haskell, you can have things like this:

    fct x y = if cond1
             then some (combinators) (applyedon largeexpression)
              else if cond2
              then largeexpression
              else Nothing
      where some x y = ...
           largeexpression = ...
            cond1 = ...
            cond2 = ...
    Haskell keeps the details in the where clause explicitly, because it knows that the elements in the where clause are evaluated when needed. In practice, the previous code is often written using guards.
    fct x y
      | cond1 = some (combinators) (applyedon largeexpression)
      | cond2 = largeexpression
      | otherwise  = Nothing
      where some x y = ...
            largeexpression = ...
            cond1 = ...
            cond2 = ...
  • In lazy evaluation, some algorithms are expressed more elegantly. For example, in the lazy version of quicksort, the cost of looking at just the first few items is proportional to the cost of selecting them.

  • Lazy evaluation lets you (re)define your own structures. In nonlazy languages, things like the following piece of code cannot be done, because both branches will be evaluated, no matter the value condition.

    if' True x y = x
    if' False x y = y
  • Elements that deal with side effects in the type system, such as monads, work only in a lazy evaluation manner.

  • Operators are short-circuited. For example, && returns false if the evaluation of the first expression is false. In this case, the second expression remains a thunk.

  • It permits interesting data structures such as infinite ones. Remember the function repeat 2 from the discussion of lists in Chapter 6.

You can find a more comprehensive description of lazy evaluation and more examples in [2].

Summary

In this chapter, you learned the following:
  • What lazy evaluation is

  • How lazy evaluation works

  • What the advantages of lazy evaluation are

References

  1. 1.

    P. Hudak, J. Hughes, S. Peyton Jones, and P. Wadler, “A History of Haskell: Being Lazy with Class,” in Proceedings of the Third ACM SIGPLAN Conference on History of Programming Languages, pp. 12–1 (ACM, 2007)

     
  2. 2.
     
  3. 3.
     
  4. 4.

    T. Takenobu, “Lazy Evaluation Illustrated for Haskell Divers,” https://takenobu-hs.github.io/downloads/haskell_lazy_evaluation.pdf

     
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.15.225.213