As many of you will know, Haskell is a non-strict language, with non-strictness implemented via the more familiar laziness. Laziness has come to define Haskell, and here I would like give an expansive view of why.

Programmers often like to harp on the soft aspects of programming languages (community, documentation), but I think Haskell presents a notable case for the technical side of things; many can say that writing Haskell is more pleasant than writing Python, but few in can articulate why. As I shall argue, it is no coincidence that Haskell has come to preëminence over Scala and its ilk, and that is due in no small part to laziness.

Part I: Imperative Programming

In part one, I would like to examine why Haskell has become the "canonical ML". The ML program, if it is to succeed, can be summarized as "programs are values" (rhyming with Lisp's "code is data"). The advantage here is that programs can be given types and in so doing, we get static guarantees that are impossible in a Lisp.

This is of course not without its downsides, but the static guarantees gained are so useful that an ML can stand toe-to-toe with Lisp⁰.

What Haskell brings to this is the oft-derided lazy IO. While many Haskell programmers (even advanced ones) will write the IO portions of their program in an imperative style, Haskell is capable of much more. Consider the following program (making use of the parallel-io package):

import Control.Concurrent.ParallelIO.Global
data Pkg = Pkg { name :: String, url :: String }
main :: IO ()
main = 
    let fetches = [ fetchPkg pkgOne, fetchPkg pkgTwo ] in
    parallel_ fetches

Crucially, we can define a sequence of actions and process that sequence by executing the actions in parallel. Here we begin to see the subtle use of monads in concert with laziness. For any side-effecting computation, merely constructing a list of such computations in a strict language will execute them! And that is the subtle benefit of lazy IO: not streaming (which is often cited), but rather the ability to treat effectful programs as values.

Indeed, we could have easily done something like

import Control.Concurrent.ParallelIO.Global
main :: IO ()
main =
    let fetches = ((x, y) -> x >> y) $ ((\p -> putStrLn "Fetching package..." ++ name p) &&& fetchPkg) [ pkgOne, pkgTwo ]
    in parallel_ fetches

which demonstrates quite poignantly that effecting computations are indeed first-class values in Haskell. The above would have been impossible to write in Rust¹, and in fact the parallel_ function can only exist in a language with laziness.

You may have heard the quip "Haskell is the best imperative language". Hopefully this gives some insight as to why. Unlike almost any other language in existence, effecting computations are values, and unlike any language in existence, effecting computations are values with types.

Part II: Symmetries

Consider the following identity:

head . fmap f = f . head

This is in fact not an identity in a strict language; if f bottoms on the second element of a list the right-hand side will bottom as well, but not the left.

Abstractions

Haskell programmers make use of laws like the above, for good reason: they make reasoning about programs (and hence writing large programs) easy. But there is another factor to consider: the ability to express abstractions that are present in mathematics. Such abstractions are much more refined by their nature, and so it often makes sense to construct programs around them (see the pipes library for an example).

Pointfree Programming

Often beginners will see something like

h = f . g

and ask why this couldn't be written as the "clearer"

h x = f (g x)

There are already reasons to write programs in a pointfree style; it has the flavor of coördinate-free treatments of geometry. But we should also recognize that it is a way of treating functions (that is, computations) as first-class objects. Consider the following Haskell taken from the recursion-schemes package:

cata :: (Base t a -> a) -- ^ a (Base t)-algebra
      -> t               -- ^ fixed point
      -> a               -- ^ result
cata f = c where c = f . fmap c . project

This again depends on laziness! Indeed, in Idris, we must write the following (from my recursion_schemes package):

cata : (Recursive f t, Base a f) => (f a -> a) -> t -> a
cata f = c 
  where c x = f . map c . project $ x

In general, eta reduction will not be valid in a strict language; we see here that it is in fact essential to treating functions as first-class values.

Functorial Programming

Functoriality is well-known in mathematics; it is what led Groethendieck to consider prime ideals rather than maximal ideas in algebraic geometry. It is present in extant Haskell as well.

Consider the hylomorphism; it can be defined as

hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
hylo f g = h where h = f . fmap h . g

Here, we have recursion that is generic among functors. This is perhaps not notable at first, but if we consider that both lists and trees are functors, it becomes apparent just how powerful this method is.

Totality

Totality is a partial answer to laziness, and for this reason I think Idris and perhaps ATS are likely the only strict languages that could inform the future of functional programming. Our previous example

head . fmap f = f . head

will hold provided that f is total. Such lawful programming is important not just because it allows us to reason about our programs, but also because it allows us to write clear programs that are nonetheless compiled to something efficient.

Part III: Efficiency

Laziness is key to writing efficient, composable programs. The classic example is

any = foldr (||) False

but other examples exist. In practice, Haskell programs tend to be slower than their strict counterparts (e.g. in OCaml), but laziness does give better tools to reason about complexity and hence amortized performance. One sacrifices the ability to reason about worst-case performance, but this is nearly always welcome when doing functional programming.

Crucially, this is also the key to doing non-strictness correctly; optimistic evaluation may be semantically correct, but its complexity is subtle.

^{1: Ironically, much like object-oriented languages being inferior to an ML when it comes to describing objects, imperative languages are inferior to Haskell when it comes to describing actions.}