Lazy evaluation

Laziness was undoubtedly the single theme that united the various groups that contributed to Haskell’s design. Once we were committed to a lazy language, a pure one was inescapable.

Hudak, P., Hughes, J., Peyton Jones, S., & Wadler, P. (2007). A History of Haskell: Being Lazy With Class

Laziness = non-strict semantics + sharing

Laziness is a common implementation technique for non-strict languages, but it is not the only possible one.

Non-strict semantics

Strict semantics:

reduce expressions from inside out, e.g. evaluating \(\times\) first in \(a+(b\times c)\)
a subexpression that evaluates to ⊥ (i.e. an error or endless loop) will be found and propagated outwards

Non-strict semantics:

reduce expressions from outside in, e.g. evaluating \(+\) first in \(a+(b\times c)\)
a subexpression that evaluates to ⊥ may be eliminated by outer reductions

With non-strict semantics we can define elegant control flow abstractions:

unless :: Applicative f => Bool -> f () -> f ()
unless True x = x
unless False _ = pure ()

any :: (Foldable f, Functor f) => (a -> Bool) -> f a -> Bool
any p = or . fmap p

unless (any isPrime [0,1..]) $ fail "No prime numbers found in ℕ!"

Haskell is one of the few modern languages to have non-strict semantics by default.

In practice, Haskell is not a purely lazy language: for instance pattern matching is usually strict. ¹

An easy way to improve performance is to call something fewer times.

Sharing stores subexpression results so that they can be reused instead of evaluated multiple times. One way to do so is using let.

In the following example, sqrt is called twice in result but only once in result':

f x y = sqrt x + y
result = f 1 2 + f 1 4

f' x = let sqrt_x = sqrt x in \y -> sqrt_x + y
result' = let f_1 = f 1 in f_1 2 + f_1 4

In the following example, fibSlow is slower than fibFast because it redefines fib' for every value of x:

fibSlow x =
    let fib 0 = 0
        fib 1 = 1
        fib n = fibSlow (n - 1) + fibSlow (n - 2)
    in  map fib [0 ..] !! x

fibFast =
    let fib 0 = 0
        fib 1 = 1
        fib n = fibFast (n - 1) + fibFast (n - 2)
    in  (map fib [0 ..] !!)

You can also use where for sharing, but the performance impact of the eta reduction becomes harder to see:

fibSlow x = map fib [0 ..] !! x
    where
      fib 0 = 0
      fib 1 = 1
      fib n = fibSlow (n - 1) + fibSlow (n - 2)

-- This eta reduction is non-trivial!
fibFast = (map fib [0 ..] !!)
    where
      fib 0 = 0
      fib 1 = 1
      fib n = fibFast (n - 1) + fibFast (n - 2)

Footnotes

1

Pattern matches can be made lazy by prepending them with ~.