19

次のようなCommon LISPでネストされた括弧を再帰的に削除するにはどうすればよいですか

  (unnest '(a b c (d e) ((f) g))) => (a b c d e f g)
  (unnest '(a b))                 => (a b)
  (unnest '(() ((((a)))) ()))     => (a)

ありがとう

4

12 に答える 12

25

これが私がすることです：

(ql:quickload "alexandria")
(alexandria:flatten list)

これは主に、Quicklispが既にインストールされているために機能します。

于 2010-11-01T01:28:28.130 に答える
15 
(defun flatten (l)
  (cond ((null l) nil)
        ((atom l) (list l))
        (t (loop for a in l appending (flatten a)))))
于 2010-04-26T10:13:48.437 に答える
8

これは古いスレッドだと思いますが、Google Lisp flatten で最初に出てくるスレッドの 1 つです。私が見つけた解決策は、上で説明したものと似ていますが、フォーマットが少し異なります。私が最初にこの質問をググったときのように、あなたがLispに不慣れであるかのように説明しますので、他の人もそうなるでしょう。

(defun flatten (L)
"Converts a list to single level."
    (if (null L)
        nil
        (if (atom (first L))
            (cons (first L) (flatten (rest L)))
            (append (flatten (first L)) (flatten (rest L))))))

Lisp を初めて使用する人のために、これは簡単な要約です。

次の行は、引数 L を指定して flatten という関数を宣言しています。

(defun flatten (L)

以下の行は、空のリストをチェックします。

    (if (null L)

cons ATOM nil は 1 つのエントリ (ATOM) を持つリストを宣言するため、次の行は nil を返します。これは再帰の基本ケースであり、いつ停止するかを関数に知らせます。この後の行は、リストの最初の項目が別のリストではなくアトムであるかどうかを確認します。

        (if (atom (first L))

次に、そうであれば、再帰を使用して、このアトムの平坦化されたリストを作成し、関数が生成する残りの平坦化されたリストと組み合わせます。cons はアトムを別のリストと結合します。

            (cons (first L) (flatten (rest L)))

それがアトムでない場合は、それをフラット化する必要があります。これは、内部にさらにリストがある可能性がある別のリストであるためです。

            (append (flatten (first L)) (flatten (rest L))))))

append 関数は、最初のリストを 2 番目のリストの先頭に追加します。また、Lisp で関数を使用するたびに、括弧で囲む必要があることに注意してください。これは最初私を混乱させました。

于 2013-11-14T01:09:11.067 に答える
7

たとえば、次のように定義できます。

(defun unnest (x)
  (labels ((rec (x acc)
    (cond ((null x) acc)
      ((atom x) (cons x acc))
      (t (rec (car x) (rec (cdr x) acc))))))
    (rec x nil)))
于 2010-04-21T07:11:35.630 に答える
7 
(defun flatten (l)
  (cond ((null l) nil)
        ((atom (car l)) (cons (car l) (flatten (cdr l))))
        (t (append (flatten (car l)) (flatten (cdr l))))))
于 2010-05-24T02:21:03.533 に答える
5

Lisp には、ものremoveを削除する機能があります。REMOVE-IFここでは、述語が true であるすべての項目を削除するバージョンを使用します。かっこであるかどうかをテストし、真の場合は削除します。

括弧を削除する場合は、次の関数を参照してください。

(defun unnest (thing)
  (read-from-string
   (concatenate
    'string
    "("
    (remove-if (lambda (c)
                 (member c '(#\( #\))))
               (princ-to-string thing))
    ")")))

ただし、Svante が言及しているように、通常は括弧を「削除」しないことに注意してください。

于 2010-04-22T09:00:11.067 に答える
2

これは、アキュムレータ ベースのアプローチです。ローカル関数%flattenは、末尾 (既に平坦化されているリストの右側の部分) のアキュムレータを保持します。平坦化されていない残りの部分 (リストの左側の部分) が空の場合は、末尾を返します。平坦化する部分がリスト以外の場合は、テールの前に付けた部分を返します。フラット化する部分がリストの場合、リストの残りを (現在のテールで) フラット化し、その結果をリストの最初の部分をフラット化するためのテールとして使用します。

(defun flatten (list)
  (labels ((%flatten (list tail)
             (cond
               ((null list) tail)
               ((atom list) (list* list tail))
               (t (%flatten (first list)
                            (%flatten (rest list)
                                      tail))))))
    (%flatten list '())))


CL-USER> (flatten '((1 2) (3 4) ((5) 6) 7))
(1 2 3 4 5 6 7)
于 2015-10-21T19:06:50.340 に答える
2

私はこの質問が本当に古いことを知っていますが、誰も push/nreverse イディオムを使用していないことに気づいたので、ここにアップロードしています.

関数reverse-atomizeは各「アトム」を取り出しoutput、次の呼び出しの に入れます。最後に、逆方向の平坦化されたリストを生成します。これは、nreverse関数内の関数で解決されatomizeます。

(defun reverse-atomize (tree output)
    "Auxillary function for atomize"
    (if (null tree)
      output
      (if (atom (car tree))
          (reverse-atomize (cdr tree) (push (car tree) output))
          (reverse-atomize (cdr tree) (nconc (reverse-atomize (car tree)
                                                               nil)
                                              output)))))

(defun atomize (tree)
    "Flattens a list into only the atoms in it"
     (nreverse (reverse-atomize tree nil)))

したがって、呼び出しatomize '((a b) (c) d)は次のようになります。

(A B C D)

そして、これを呼び出すreverse-atomizeと、次のreverse-atomize '((a b) (c) d)ようになります。

(D C B A)

push、nreverse、 などの関数を使用するのが好きな人nconcは、それぞれconsの 、reverse、およびappend関数よりも RAM の使用量が少ないためです。そうは言っても、の二重再帰的な性質にreverse-atomizeは、独自のRAM化が伴います。

于 2016-02-15T02:00:33.363 に答える
2

この人気のある質問には、再帰的な解決策しかありません (Rainer の回答は数えません)。

ループバージョンを作りましょう:

(defun flatten (tree &aux todo flat)
  (check-type tree list)
  (loop
     (shiftf todo tree nil)
     (unless todo (return flat))
     (dolist (elt todo)
       (if (listp elt)
           (dolist (e elt)
             (push e tree))
           (push elt flat))))))
于 2020-04-08T20:49:55.053 に答える
1 
(defun unnest (somewhat)
  (cond
   ((null somewhat) nil)
   ((atom somewhat) (list somewhat))
   (t
    (append (unnest (car somewhat)) (unnest (cdr somewhat))))))
于 2012-07-31T10:59:45.570 に答える