Common Lispの効率的なcollect関数

Question

私はLispを学んでおり、次の関数を書いて結果のリストを収集しています。

(defun collect (func args num) 
    (if (= 0 num) 
    () 
     (cons (apply func args) 
     (collect func args (- num 1))))) 

組み込みループ関数と同様の出力を生成します。私はループのバージョンは私が作ることができる方法ではない

CL-USER> (length (loop repeat 100000 collect (random 5))) 
100000 

ないのに対し

CL-USER> (length (collect #'random '(5) 100000)) 
Control stack guard page temporarily disabled: proceed with caution 

10万要素の長いリストを生成しようとすると、

CL-USER> (collect #'random '(5) 10) 
(4 0 3 0 1 4 2 1 0 0) 
CL-USER> (loop repeat 10 collect (random 5)) 
(3 3 4 0 3 2 4 0 0 0) 

しかし私コレクト機能は、スタックを吹きますより効率的なバージョンのバージョン、consingの代替手段はありますか？私はそれが尾を再帰的だと思う。私はsbclを使用しています。どんな助けも素晴らしいだろう。

Answer 1

一般的なLispの実装は、テールコールの最適化を行うためにANSI標準では必要ありません。しかし、その塩の価値があるもの（SBCLを含む）の大半は最適化されます。

あなたの関数は、テール再帰的ではありません。彼らはそれにrecpectで一定であるので

 
    (defun collect (func args num) 
     (labels ((frob (n acc) 
       (if (= 0 n) 
        acc 
        (frob (1- n) (cons (apply func args) acc))))) 
     (frob num nil))) 

（オリジナルパラメータFUNCとARGSをローカル関数に除去される。これは、中間結果を蓄積するための追加のパラメータを導入する一般的なトリックを用いて1に変換することができ）。

Answer 2

まあ、再帰の代替は反復です。

Common Lispはスキームとは異なり、実装者からの末尾再帰を必要としないことを知っておくべきです。

(defun mycollect (func args num) 
    (let ((accumulator '()))  ; it's a null list. 
    (loop for i from 1 to num 
     do 
     ;;destructively cons up the accumulator with the new result + the old accumulator 
     (setf accumulator     
     (cons (apply func args) accumulator))) 
    accumulator))    ; and return the accumulator 

Answer 3

いいえ、テール再帰的ではありません。 ANSI Common Lispはそれもあなたのコードについては何も言いませんどちらも：

(defun collect (func args num) 
    (if (= 0 num) 
    () 
     (cons (apply func args) 
      (collect func args (- num 1))))) 

あなたのコードを見れば、収集するためにあなたの呼び出しの周りCONSがあります。このCONSは、COLLECTへの再帰呼び出しの値を受け取ります。したがって、COLLECTは尾を再帰的にすることはできません。アキュムレータ変数を導入することで、テール再帰的に見えるものに関数を書き直すのは比較的簡単です。さまざまなLispやSchemeの文献にそのことを記述してください。

反復計算をプログラムするデフォルトの方法は、いくつかの反復構造の一つ使用しているCommon Lispでは

：DO、DOTIMES、DOLIST、LOOP、MAP、でmapcarを、...

のCommon Lisp標準にはありませんテールコール最適化（TCO）を提供します。他のいくつかの言語機能の存在下でTCOが何をすべきかを指定する必要があります。たとえば、動的バインディングや特殊変数はTCOに影響します。しかしCommon Lispの標準では、一般的なTCOやTCOの影響については何も言及していません。 TCOはANSI Common Lisp標準の一部ではありません。

いくつかのCommon Lispの実装には、コンパイラスイッチでさまざまなテールコール最適化を有効にする方法があります。これらを有効にする方法と制限の両方は実装固有のものであることに注意してください。

概要：Common Lispでは反復構造を使用し、再帰は使用しません。

(defun collect (func args num) 
    (loop repeat num 
     collect (apply #'func args))) 

ボーナスが追加されました。読みやすくなりました。