Land of Lisp: Simple Lazy List Functions

lazy.lisp

;;;;

(defmacro lazy (&body body)
  "Lazily evaluate BODY."
  (let ((forced (gensym))
        (value (gensym)))
    `(let ((,forced nil)
           (,value nil))
       (lambda ()
         (unless ,forced
           (setf ,value (progn ,@body))
           (setf ,forced t))
         ,value))))

(defun force (lazy-value)
  "Force the evaluation of LAZY-VALUE."
  (funcall lazy-value))

(defmacro lazy-cons (a d)
  "Lazily CONS A onto B."
  `(lazy (cons ,a ,d)))

(defun lazy-car (x)
  (car (force x)))

(defun lazy-cdr (x)
  (cdr (force x)))

(defun lazy-nil ()
  (lazy nil))

(defun lazy-null (x)
  (not (force x)))

(defun make-lazy (lst)
  (lazy (when lst
          (cons (car lst) (make-lazy (cdr lst))))))

(defun take (n lst)
  "Take the first N items from LST."
  (unless (or (zerop n)
              (lazy-null lst))
    (cons (lazy-car lst)
          (take (1- n)
                (lazy-cdr lst)))))

(defun take-all (lst)
  "Take all the items from LST."
  (unless (lazy-null lst)
    (cons (lazy-car lst)
          (take-all (lazy-cdr lst)))))

(defun lazy-mapcar (fn lst)
  (lazy (unless (lazy-null lst)
          (cons (funcall fn (lazy-car lst))
                (lazy-mapcar fn (lazy-cdr lst))))))

(defun lazy-mapcan (fn lst)
  (labels ((f (l)
             (if (lazy-null l)
                 (force (lazy-mapcan fn (lazy-cdr lst)))
                 (cons (lazy-car l)
                       (lazy (f (lazy-cdr l)))))))
    (lazy (unless (lazy-null lst)
            (f (funcall fn (lazy-car lst)))))))

(defun lazy-find-if (fn lst)
  (unless (lazy-null lst)
    (let ((x (lazy-car lst)))
      (if (funcall fn x)
          x
          (lazy-find-if fn (lazy-cdr lst))))))

(defun lazy-nth (n lst)
  (if (zerop n)
      (lazy-car lst)
      (lazy-nth (1- n) (lazy-cdr lst))))