Lazy evaluation

The history of Haskell is deeply entwined with the history of 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."
	--History of Haskell, Hudak et al

Thanks to lazy evaluation, we can still consume the undoomed part of this list:

doomedList = [2, 3, 5, 7, undefined]
take 0 xs = []
take n (x:xs) = x : (take (n-1) xs)

main = do print (take 4 doomedList)

The take object is lazy because the cons operator (:) is lazy, which is because all functions in Haskell are lazy by default.

A lazy cons evaluates only its first argument, while the second argument, the tail, is only evaluated when it is selected. (For strict lists, both head and tail are evaluated at the point of construction of the list.)

The proxy pattern has several motivations, one of which is to defer evaluation; this aspect of the proxy pattern is subsumed by lazy evaluation.

Streams

The simple idea of laziness enables has the profound effect of enabling self-reference:

infinite42s = 42 : infinite42s

Streams (lazy lists) simulate infinity through "the promise of potential infinity" [Why Functional Programming Matters, Hughes]:

potentialBoom = (take 5 infinite42s)

A stream is always just one element cons'ed to a tail of whatever size. A function such as take consumes its input stream but is decoupled from the producer of the stream to such an extent that it doesn't matter whether the stream is finite or infinite (unbounded). Let's see this in action with a somewhat richer example:

generate :: StdGen -> (Int, StdGen)
generate g = random g :: (Int, StdGen)

-- import System.Random
main = do
  gen0 <- getStdGen
  let (int1, gen1) = (generate g)
  let (int2, gen2) = (generate gen1)

Here we are generating a random int value and returning a new generator, which we could use to generate a subsequent random int value (passing in the same generator would yield the same random number).

Carrying along the generator from one call to the next pollutes our code and makes our intent less clear. Let's instead create a producer of random integers as a stream:

randInts' g = (randInt, g) : (randInts' nextGen)
       where (randInt, nextGen) = (generate g)

Next, suppress the generator part of the stream by simply selecting the first part of the tuple:

randInts g = map fst (randInts' g)
main = do
  g <- getStdGen
  print (take 3 (randInts g))

We still pass in the initial generator to the stream, but now we can consume independently from producing the numbers. We could just as easily now derive a stream of random numbers between 0 and 100:

randAmounts g = map (\x -> x `mod` 100) (randInts g)

This is why it is said that lazy lists decouple consumers from producers. From another perspective, we have a decoupling between iteration and termination. Either way, we have decoupling, which means we have a new way to modularize and structure our code.

Modeling change with streams

Consider a banking system, where we want to record the current balance of a customer's account. In a non-pure functional language, we would typically model this with a mutable variable for the balance: for each debit and credit in the "real world", we would mutate the balance variable.

"Can we avoid identifying time in the computer with time in the modeled world?"

[Structure and Interpretation of Computer Programs, p. 316], Abelson and Sussman

Yes, we can describe the evolution of a variable as a function of time. Instead of a mutable variable for bank balance, we have a sequence of balance values. In other words, we replace a mutable variable with the entire history of states:

bankAccount openingB (amt:amts)
  = openingB : bankAccount (openingB + amt) amts

(take 4 (bankAccount 0 [-100, 50, 50, 1]))

Here we have modeled the bank account as a process, which takes in a stream of transaction amounts. In practice, amounts are more likely to be an unbounded stream, which we can easily simulate with our randAmounts stream from earlier:

(take 4 (bankAccount 0 (randAmounts g)))

	"if we concentrate on the entire time history, we do not emphasize change"
	--[Structure and Interpretation of Computer Programs, p. 317], Abelson and Sussman

Lazy evil

Streams provide an antidote to mutation, but as with all powerful medicine, streams create new problems. Because streams pretend to express a complete list while only incrementally materializing the list, we cannot know exactly when evaluation of list elements happens. In the presence of side effects, this ignorance of the order of events becomes a serious problem. We will devote the next chapter to dealing with mutation in the presence of laziness.