[解決済み] Lispの逆引きリスト

質問

Lispでリストを反転させようとしているのですが、次のようなエラーが発生します。例外 C0000005 [flags 0] at 20303FF3 {オフセット 25 内 #} eax 108 ebx 200925CA ecx 200 edx 2EFDD4D esp 2EFDCC8 ebp 2EFDCE0 esi 628 edi 628 "

私のコードは以下の通りです。

(defun rev (l)
    (cond
        ((null l) '())
        (T (append (rev (cdr l)) (list (car l)))))) 

何が間違っているのか、どなたか教えてください。ありがとうございます。

解決方法は？

あなたの書いたコードは論理的に正しく、あなたが望むような結果を生み出します。

CL-USER> (defun rev (l)
           (cond
             ((null l) '())
             (T (append (rev (cdr l)) (list (car l)))))) 
REV
CL-USER> (rev '(1 2 3 4))
(4 3 2 1)
CL-USER> (rev '())
NIL
CL-USER> (rev '(1 2))
(2 1)

とはいえ、性能面ではいくつか問題があります。 その アペンド 関数は、最終引数以外のすべてのコピーを生成します。 例えば (append '(1 2) '(a b) '(3 4))) 最後のcdrは既存のリスト(3 4)です。 これは アペンド はこのようなものです。

(defun append (l1 l2)
  (if (null l1)
      l2
      (cons (first l1)
            (append (rest l1)
                    l2))))

これは、Common Lispの アペンド というのも、Common Lispの アペンド は2つ以上の引数を取ることができます。 しかし、最後のリスト以外がコピーされる理由を示すには、十分近いものです。 では、このことが、あなたが実装している レヴ とはいえ。

(defun rev (l)
  (cond
    ((null l) '())
    (T (append (rev (cdr l)) (list (car l)))))) 

つまり、以下のようなリストを反転させるときに (1 2 3 4) は、あなたがいるようなものです。

(append '(4 3 2) '(1))              ; as a result of    (1)
(append (append '(4 3) '(2)) '(1))  ; and so on...      (2)

さて、(2)行目では、リスト(4 3)をコピーしていますね。 行目では、(4 3)のコピーを含むリスト(4 3 2)をコピーしています。 つまり、あなたは コピーをコピーする . これはかなり無駄なメモリの使い方ですね。

より一般的な方法は、アキュムレータ変数とヘルパー関数を使う方法です。 (なお、私は エンドプ , 休憩 , 最初 そして リスト の代わりに ヌル , cdr , 車 そして 短所 これは、任意のcons-treeではなく、リストを扱っていることを明確にするためです。 これらはほとんど同じです(ただし、いくつかの違いがあります)。

(defun rev-helper (list reversed)
  "A helper function for reversing a list.  Returns a new list
containing the elements of LIST in reverse order, followed by the
elements in REVERSED.  (So, when REVERSED is the empty list, returns
exactly a reversed copy of LIST.)"
  (if (endp list)
      reversed
      (rev-helper (rest list)
                  (list* (first list)
                         reversed))))

CL-USER> (rev-helper '(1 2 3) '(4 5))
(3 2 1 4 5)
CL-USER> (rev-helper '(1 2 3) '())
(3 2 1)

このヘルパー関数を使うと、簡単に レヴ :

(defun rev (list)
  "Returns a new list containing the elements of LIST in reverse
order."
  (rev-helper list '()))

CL-USER> (rev '(1 2 3))
(3 2 1)

とはいえ、外部のヘルパー関数を用意するよりも、おそらくは ラベル を使用して、ローカルヘルパー関数を定義します。

(defun rev (list)
  (labels ((rev-helper (list reversed)
             #| ... |#))
    (rev-helper list '())))

また、Common Lispはtailコールを最適化することを保証していないので する ここでもループがきれいでいい。

(defun rev (list)
  (do ((list list (rest list))
       (reversed '() (list* (first list) reversed)))
      ((endp list) reversed)))