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. 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 non-trivial!
fibFast = (map fib [0 ..] !!)
where
fib 0 = 0
fib 1 = 1
fib n = fibFast (n - 1) + fibFast (n - 2)
- Lazy vs. non-strict - 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
~
.