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の文と余分な変数を組み合わせて、メソッドが初めて呼び出されたかどうかを確認できますが、それは醜いようです。それを行うより良い方法は何ですか？

Answer 1

Common Lispにyieldという直接的な同等物はありません。いくつかの機能的アプローチを使用するか、遅延計算を提供する何らかの種類のライブラリを使用するかもしれません。

あなたのアプローチを完了する1つの方法は、現在の継続を保持する変数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))