2

ネストされたリストを元のリストに戻る数値に凝縮する方法を見つけようとしていますが、問題が発生しています。

私は、ここで与えられている flatten 関数 (非常に広く利用可能) を見てきました:

(defun flatten (l)
  (cond
    ((null l) nil)
    ((atom l) (list l))
    (t (loop for a in l appending (flatten a)))))

この例が再帰であることは理解していますが、どのように機能しますか? 要素が null かアトムかをチェックしますが、要素がこれらの条件に当てはまる場合はどうするのでしょうか?

4

3 に答える 3

4

(loop for a in l appending (g a))私の時代には、私たちが書いた代わりに(mapcan #'g l)。(apply #'append (mapcar #'g l))多かれ少なかれ同等です：

(defun flatten (l) 
    (if l 
        (if (atom l) 
            (list l) 
            (mapcan #'flatten l))))

では、この場合はどういう意味ですか？を呼び出すと想像してください(flatten (list 1 2 3 4 5))。つまり、引数リストにはアトムしかありません。そのリスト内の各アトムはリストに囲まれます-などのようにシングルトン リスト(1) (2)になります。その後、それらはすべて一緒に追加され、元のリストが返されます:

(  1   2   3   4   5  )

( (1) (2) (3) (4) (5) )

(  1   2   3   4   5  )

したがって、アトムのリストを平坦化することは同一性操作です (Common LISP では、それは です#'identity)。ここで、いくつかのアトムとアトムのリストを含むリストをフラット化することを想像してください。繰り返しますが、リストの各要素は によって変換され、すべて一緒に追加されます。先ほど見たように、アトムのリストはそれ自体のままです。アトムはそれぞれリストに含まれます。したがって、追加すると、ネストされたリストの両方のレベルにあったすべてのアトムが返され、フラット化されます。flatten

(  11   12  (1 2 3 4)  13  )

( (11) (12) (1 2 3 4) (13) )

(  11   12   1 2 3 4   13  )

などなど、より多くのネストのレベルについても同様です。

NILリスト内の要素としての s は問題を引き起こします。NILは空のリストであり、空のリストには何も含まれていないため、何も提供しないでください。しかしNIL、原子でもあります。そのため、それをシングルトン リストに含めないように、特別なケースを作成します。そのままにしておくと、追加されたときに消えてしまいます。

于 2012-05-05T20:55:27.950 に答える
3 
(defun flatten (l)

FLATTEN上記は、と呼ばれる1つの引数を持つ関数を定義していますL。

  (cond

もしも

    ((null l) nil)

引数の値はL空のリストです。空のリストを返します。

    ((atom l) (list l))

または、引数Lがアトム（つまりリストではない）の場合は、アトムを唯一の項目として含むリストを返します。

    (t

または、空でないリストがあります

       (loop for a in l

次に、の値であるリスト内のすべてのアイテムをループしますL

        appending (flatten a)

各リスト項目を平坦化した結果を追加します。

))))
于 2012-05-05T21:24:45.700 に答える
2

  1. 見ている要素がnilリストの最後である場合は、nil を返します。

  2. 見ている要素がリストではない場合、その要素を含むリストを返します（リストではないアトムを指定すると、アトム自体ではなく、アトム)。

  3. それ以外の場合 (リストの場合)、そのすべての要素をループし、すべての平坦化されたサブツリー ( を呼び出して平坦化したものflatten) を追加してから、それらを返します。

これは短いですが、最も効率的なアルゴリズムではありません。なぜなら、ある部分を別の部分の末尾にコンスするには、append をリストの最後まで行う必要があるからです。以下は少し複雑ですが、より効率的なバージョンのように見えます。

(defun flatten (x &optional y)
  (cond
    ((null x)
     (cond
       ((null y) nil)
       ((listp (car y))
        (flatten (car y) (cdr y)))
       (t (cons (car y) (flatten (cdr y))))))
    ((listp (car x))
     (flatten (car x) (if y (list (cdr x) y) (cdr x))))
    (t (cons (car x) (flatten (cdr x) y)))))

この関数の背後にあるアルゴリズムは、次のように処理します。

  1. 最初の要素も残りの要素もない場合 - すべてを実行したので、nil(リストの最後) を返します。

  2. 最初の要素がない場合 - 2 番目の要素を最初の要素と残りの要素に分割して繰り返します。

  3. 最初の要素がある場合はそれをリストに入れ、2 番目の要素がある場合は保持し、そうでない場合は次の要素を選択して繰り返します。

編集：解釈が本当に曖昧だった/間違っている可能性があるため、＃3を変更しました。

于 2012-05-05T20:35:56.813 に答える