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 ..

1
2
3

> let naturals = [1..]
> take 5 naturals
[1,2,3,4,5]

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

1
2
3

 > let squares = [x*x | x <- naturals]
 > take 5 squares
[1,4,9,16,25]

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:

1
2
3
4
5

take 0 _  = []
take n (x:xs) = x :: take (n - 1) xs

> take 2 [1,2,3]
[1,2]

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:

1
2
3
4
5
6
7

(define naturals
      (cons 1
            (cons 2
                  (cons 3
                        (lambda ()
                          ; a function which returns naturals till infinity
                          ))))))

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 current-value).

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.

1
2
3
4
5
6

(define naturals
  (let ((init 1))
    (define (next current)
      (lambda () (cons current
                       (next (+ 1 current)))))
    (next init)))

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.

1
2
3
4
5
6

> (naturals)
'(1 . #<procedure>)
>(cdr (naturals))
#<procedure>
> ((cdr (naturals)))
'(2 . #<procedure>)

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!

1
2
3
4
5
6

(define (take n stream)
  (if (= n 0)
      null
      (let ((thunk (stream)))
        (cond ; this has to be a proper list
              (else (cons (car thunk) (take (- n 1) (cdr thunk))))))))

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

1
2
3
4

(define powers-of-two
  (let ((init 2))
    (define (next current) (lambda () (cons current (next (* 2 current)))))
    (next init)))

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:

1
2
3
4

(define (create-stream init f)
  (define (next current)
    (lambda () (cons current (next (f current)))))
  (next init))

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

1
2
3

(define powers-of-three
  (create-stream 3
                 (lambda (current) (* 3 current))))

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

1
2
3
4

(define fib-stream
   (let ((l1 1) (l2 1))
     (define (next v1 v2) (lambda () (cons v1 (next v2 (+ v1 v2)))))
     (next l1 l2)))

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

1
2

> (take 12 fib-stream)
'(1 1 2 3 5 8 13 21 34 55 89 144)

PS: A large portion of this post came up because of the excellent Programming Language course taught by Prof. Dan Grossman.