懒惰地在Common Lisp中生成素数

Question

我试图用pythonic方式生成素数 - 也就是说,使用生成器.

python代码或多或少会有以下几点

def divisor_in_list(n, d):
    """ Returns true if a divisor of n is in d, false otherwise"

def primes():
    yield 2
    primelist = [2]
    i = 3

    while True:
        while divisor_in_list(i, primelist):
            i += 2
        primelist.append(i)
        yield i

我是Lisp的新手,所以我想知道惯用的等价物是什么.根据我的研究到目前为止,我有以下代码

(defun primes ()
  (let* ((p (list 2)) (n 3))
    (lambda ()
      (loop while (divisor-in-slist n p)
            do (incf n 2))
      (nconc p (list n))
      (+ n 0) ;; Not actually sure how to return N directly :(
      )
    )
  )

但是,这个代码存在一个问题,即它吐出的第一个值是3.不幸的是,我还没有弄清楚如何优雅地修改它以产生2作为第一个值.

我绝对可以if在lambda和一个额外的变量中组合一个语句,以检查该方法是否第一次被调用,但这看起来很难看.有什么更好的方法呢？

Answer 1

yield在Common Lisp中没有直接的等价物.人们可能会使用某种功能方法或使用某种提供延迟计算的库.

完成你的方法的一种方法是这样的,我们有一个f保持当前延续的变量.

(defun make-prime-generator (&aux (p (list 2)) (n 2) f)
  (labels ((f2 ()            ; a function for the first iteration
             (incf n)
             (setf f #'fn)   ; setting f to the next function
             2)
           (fn ()            ; a function for all other iterations
             (loop while (divisor-in-list n p)
                   do (incf n 2))
             (push n p)
             n))
    (setf f #'f2)            ; setting f to the first function
    (lambda ()               ; returning a closure
      (funcall f))))         ;   which calls the current f


CL-USER 28 > (let ((p (make-prime-generator)))
               (flet ((p () (funcall p)))
                 (loop repeat 10 do (print (p)))))

2 
3 
5 
7 
11 
13 
17 
19 
23 
29 
NIL

如果一个人雄心勃勃,那么可以隐藏在宏的背后,这将定义所有代码部分并管理转换.

进一步探索

我们可以通过引入本地函数使状态更改更加明确init,exit并且step.

(defun make-prime-generator (&aux (p (list 2)) (n 2) f)
  (flet ((init (function)
           (setf f function))
         (exit (result function)
           (setf f function)
           result)
         (step ()
           (funcall f)))
    (labels ((f2 ()
               (incf n)
               (exit 2 #'fn))
             (fn ()
               (loop while (divisor-in-list n p)
                     do (incf n 2))
               (push n p)
               (exit n #'fn)))
      (init #'f2)
      #'step)))

现在这将是另一个稍微更高级的任务:编写一个宏gen-run,它允许我们删除样板并使代码更具说明性.它可能像这样使用:

(defmacro gen-run (f-descriptions &key start)
  (let ((§f    (gensym "F"))
        (§init (gensym "INIT"))
        (§exit (gensym "EXIT"))
        (§step (gensym "STEP")))
    `(let (,§f)
       (flet ((,§init (function)
                (setf ,§f function))
              (,§exit (result function)
                (setf ,§f function)
                result)
              (,§step ()
                (funcall ,§f)))
         (labels (,@(loop for fd in f-descriptions
                      collect (destructuring-bind (name -> next &body body)
                                  fd
                                (declare (ignore ->))
                                `(,name ()
                                    (,§exit ((lambda () ,@body))
                                            (function ,(if next next name)))))))
           (,§init (function ,start))
           (function ,§step))))))

(defun make-prime-generator (&aux (p (list 2)) (n 2))
  (gen-run ((f2 -> fn
              (incf n)
              2)
            (fn -> fn
              (loop while (divisor-in-list n p)
                    do (incf n 2))
              (push n p)
              n))
      :start f2))