[blog] | [projects] | [about] | [imprint]

Lazy-sequences

07 January 2021
 

Lazy (evaluated) sequences are sequences whose elements are generated on demand. Many languages have them built in or available as libraries.

If you don't know what this is then here is an example:

(take 5 (range :from 100))
(100 101 102 103 104)

take takes the first 5 elements from the a generator range which starts counting at 100. Each 'take' makes the range generator compute a new value rather then computing 5 elements up-front.

That's why it is called 'lazy'. The elements of the sequence are computed when needed. In a very simple form lazy evaluated sequences can be implemented using a generator that we call range and a set of consumers, like take. The generator can be implemented in a stateful way using a 'let over lambda', like this:

(defun range (&key (from 0))
  (let ((n from))
    (lambda () (prog1
              n
            (incf n)))))

The range function returns a lambda which has bound the n variable (this is also called 'closure'). When we now call the the lambda function it will return n and increment as a last step. (The prog1 form returns the first element and continues to evaluate the rest)

So we can formulate a take function like this:

(defun take (n gen)
  (loop :repeat n
        :collect (funcall gen)))

take has two arguments, the number of elements to 'take' and the generator, which is our lambda from range. This is a very simple example but effectively this is how it works.

If you are looking for good libraries for Common Lisp then I can recommend the following two:

  1. gtwiwtg: a new kid on the block.
  2. Series: a well known and solid library.
[atom/rss feed]