Adding Generators to Common Lisp

(defmacro doseq((var seq) &body body)
  (let ((seq-name (gensym))   ; Генерируем имя переменной хранящей seq
        (stop-name (gensym))) ; Генерируем имя для флага

    `(let ((,seq-name ,seq)) ; Сохраняем seq в переменную
       ;; Бесконечный цикл
       (do () (nil) 
         ;; Получаем новый элемент и флаг
         (multiple-value-bind (,var ,stop-name) (next ,seq-name)
           (when ,stop-name ; Если флаг поднят, выходим из цикла
             (return))
           ,@body))))) ; Исполняем тело цикла

And now for iterations we can write like this:

CL-USER> (doseq (x (range 3))
           (print x))

0 
1 
2 
NIL

Advanced functions for working with sequences

Let’s add some functionality to our code. Let’s start lazy map. So that the code does not conflict with the functions built into CL, we will add the letter l (lazy) in the name

(defun lmap(fn seq)
  (make-lazy-seq
   (lambda ()
     (multiple-value-bind (elem stop?) (next seq)
       (if stop?
           (values nil t)
           (values (funcall fn elem) nil))))))

While there are values ​​in the initial sequence, we extract them, pass them through the function and return them. If there are no values, we end the sequence.

Function lfilter takes a predicate and a sequence and leaves only that which satisfies the predicate in the sequence

(defun lfilter(fn seq)
  (make-lazy-seq
   (lambda ()
     (do () (nil)
       (multiple-value-bind (elem stop?) (next seq)
         (when stop?
           (return (values nil t)))
         (when (funcall fn elem)
           (return (values elem nil))))))))

Here when calling the function nextwe pull values ​​from the initial sequence until they run out or until the filter function returns true.

You can also define a function for gluing sequences

(defun lappend(&rest seqs)
  (let ((index 0))
    (make-lazy-seq
     (lambda ()
       (do () (nil)
         (unless (< index (length seqs))
           (return (values nil t)))

         (multiple-value-bind (elem stop?) (next (nth index seqs))
           (unless stop?
             (return (values elem nil)))
           (incf index)))))))

It sequentially gets all the elements from the current sequence and moves on to the next one. Repeats until the sequence ends.

Now you can write more complex generators, for example:

(lappend (lfilter #'oddp (range 10)) 
         (lfilter #'evenp (range 10)))

This is a generator that first passes through all odd numbers from 0 to 10, and then through all even (not inclusive)

Endless Sequences

Surprisingly, sometimes creating infinite sequences is easier than creating finite ones. The generator of all non-negative integers is obtained from range putting away if

(defun numbers()
  (let ((iter -1))
    (make-lazy-seq
     (lambda ()
       (incf iter)))))

The generator of all primes is pretty fun too. We need to define a primality test function and use a lazy filter to sift all natural numbers through it.

(defun is-prime(n)
  (do ((i 2 (+ 1 i)))
      ((> i (sqrt n)) t)
    (when (= 0 (mod n i))
      (return-from is-prime nil))))

(defun primes()
  (let ((base-seq (numbers)))
    (next base-seq) ; пропускаем 0 и 1
    (next base-seq) 
    (lfilter #'is-prime base-seq)))

That’s all I have for now. I highly recommend that readers try to write infinite recurrent generators (like ones = 1 : ones from Haskell). The topic is interesting, but so far my implementation is lame, so it’s not good for an article.
Thank you for your attention

(defclass lazy-seq ()
  ((next-fn :accessor seq-next-fn
            :initarg :next-fn)))

(defun make-lazy-seq(&optional next-fn)
  (make-instance 'lazy-seq :next-fn next-fn))

(defun next(seq)
  (funcall (seq-next-fn seq)))

(defun range(n)
  (let ((iter -1))
    (make-lazy-seq
     (lambda ()
       (incf iter)
       (if (< iter n)
           (values iter nil)
           (values nil t))))))

(defun numbers()
  (let ((iter -1))
    (make-lazy-seq
     (lambda ()
       (incf iter)))))

(defun is-prime(n)
  (do ((i 2 (+ 1 i)))
      ((> i (sqrt n)) t)
    (when (= 0 (mod n i))
      (return-from is-prime nil))))

(defmacro doseq((var seq) &body body)
  (let ((seq-name (gensym))   ; Генерируем имя переменной хранящей seq
        (stop-name (gensym))) ; Генерируем имя для флага

    `(let ((,seq-name ,seq)) ; Сохраняем seq в переменную
       ;; Бесконечный цикл
       (do () (nil) 
         ;; Получаем новый элемент и флаг
         (multiple-value-bind (,var ,stop-name) (next ,seq-name)
           (when ,stop-name ; Если флаг поднят, выходим из цикла
             (return))
           ,@body))))) ; Исполняем тело цикла

(defun lmap(fn seq)
  (make-lazy-seq
   (lambda ()
     ;; Извлекаем значение из исходной последовательности
     (multiple-value-bind (elem stop?) (next seq)
       (if stop?
           (values nil t) 
           (values (funcall fn elem) nil))))))

(defun lfilter(fn seq)
  (make-lazy-seq
   (lambda ()
     (do () (nil)
       (multiple-value-bind (elem stop?) (next seq)
         (when stop?
           (return (values nil t)))
         (when (funcall fn elem)
           (return (values elem nil))))))))

(defun lappend(&rest seqs)
  (let ((index 0))
    (make-lazy-seq
     (lambda ()
       (do () (nil)
         (unless (< index (length seqs))
           (return (values nil t)))

         (multiple-value-bind (elem stop?) (next (nth index seqs))
           (unless stop?
             (return (values elem nil)))
           (incf index)))))))

(defun primes()
  (let ((base-seq (numbers)))
    (next base-seq)
    (next base-seq)
    (lfilter #'is-prime base-seq)))