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 = nonstrict semantics + sharing
Laziness is a common implementation technique for nonstrict languages, but it is not the only possible one.
Nonstrict 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
Nonstrict 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 nonstrict 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 nonstrict semantics by default.
In practice, Haskell is not a purely lazy language: for instance pattern matching is usually strict. ^{ 1 }
Sharing
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 nontrivial!
fibFast = (map fib [0 ..] !!)
where
fib 0 = 0
fib 1 = 1
fib n = fibFast (n  1) + fibFast (n  2)
 Lazy vs. nonstrict  Haskell Wiki
 Performance/Laziness  Haskell Wiki
 Let vs. Where  Haskell Wiki
 Mitchell, N. (2011). Sharing in Haskell

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