Programming Laziness
Contents
Haskell makes lazy evaluation of data pretty easy, and the same can be implemented in other programming languages which treat functions as first class citizens.
In order to add laziness to the structure, we need to understand that a
lazy data structure is made up of a value and a computation. Unlike an
array, we cannot skip n
values and go directly to n+1
value; we have
to iterate the entire n values and then reach the next value.
In the following code, we are creating an infinite stream of values. The
initial value is 1, and (predefined) computation comes in the form of
..


Using list comprehensions, we have the option of creating our own streams, which are again infinite.


take
is supposed to work with infinite streams, but since every list
can possibly be infinite in Haskell due to the lazy nature of the
language, it is trivial to define:


For languages which are eager by nature, the concept of lazy data structures can also be added on top.
Taking the example of Racket, we have the option of creating a lazy list out of the versatile cons cells.
Squinting the eyes hard enough, we can see that the naturals
list is
simply:


We have the initial value, and now need to derive the computation which gives us the next value based on the current value. In this case, it is (+ 1 currentvalue).
Like I mentioned before, languages which treat functions as first class provide the semantics of storing them. And here we will be storing the computational function which returns a cons cell with the current value and a copy of itself to provide the next value (and a copy of itself which can provide the next value (and a copy …)).
See that the second of cons pair is a function. This is because
functions are evaluated only when called, not when defined. So the next
value will not be calculated unless the lambda is called. This mechanism
is called a “thunk”. Replacing the lambda with just a call to next
(next (+ 1 current))
will result in an infinite loop.


So naturals
in racket is not as concise as it was in Haskell, but this
is good enough in its own right. Also, unlike haskell code, here
naturals
is a function, calling which will return a cons containing
the current value and a procedure to fetch the next value.


The take
function is also not as concise as the one found in Haskell,
but it will not stop us from creating one in Racket, for (Computer)
Science!


We can go ahead and create a stream which gives us powers of two:


Of course, we are intelligent enough to see that there’s a common pattern emerging here. What these 2 streams differ in are the initial values and their computation functions.
Let us create a factory function for streams:


This can now be used to create streams which increment the previous value with newer values.


For more complicated streams, like Fibonacci number stream, we cannot use createstream since it depends on two values. But anyhow, we know how to create it:


But take
function still works since the basic mechanism of streams is
the same: =cons=ed value and computation.


PS: A large portion of this post came up because of the excellent Programming Language course taught by Prof. Dan Grossman.
Author Tushar Tyagi
LastMod Aug 5, 2016