Как удалить вложенные скобки в LISP

Вот что я бы сделал:

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

Это работает главным образом потому, что у меня уже установлен Quicklisp.

Я понимаю, что это старая тема, но она одна из первых, которая появляется, когда я гуглю lisp flatten. Решение, которое я обнаружил, похоже на те, что обсуждались выше, но форматирование немного отличается. Я объясню это так, как будто вы новичок в 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, это краткое изложение.

В следующей строке объявляется функция flatten с аргументом L.

(defun flatten (L)

Строка ниже проверяет наличие пустого списка.

    (if (null L)

Следующая строка возвращает nil, потому что cons ATOM nil объявляет список с одной записью (ATOM). Это базовый случай рекурсии, который сообщает функции, когда следует остановиться. Строка после этого проверяет, является ли первый элемент в списке атомом, а не другим списком.

        (if (atom (first L))

Затем, если это так, он использует рекурсию для создания сглаженного списка этого атома, объединенного с остальной частью сглаженного списка, который сгенерирует функция. cons объединяет атом с другим списком.

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

Если это не атом, то мы должны сгладить его, потому что это другой список, внутри которого могут быть дополнительные списки.

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

Функция добавления добавит первый список к началу второго списка. Также обратите внимание, что каждый раз, когда вы используете функцию в lisp, вы должны заключать ее в круглые скобки. Меня это сначала смутило.

Вы можете определить это, например, так:

(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)))

В Лиспе есть функция remove для удаления вещей. Здесь я использую версию REMOVE-IF, которая удаляет все элементы, для которых предикат истинен. Я проверяю, является ли это скобкой, и удаляю ее, если она верна.

Если вы хотите удалить круглые скобки, см. эту функцию:

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

Обратите внимание, однако, как упоминает Сванте, обычно не «удаляют» круглые скобки.

Просто оставив это здесь, поскольку я посетил этот вопрос с необходимостью выравнивания только одного уровня, а позже выяснил для себя, что (apply 'concatenate 'list ((1 2) (3 4) (5 6 7))) является более чистым решением в этом случае.

В большинстве ответов уже упоминалось рекурсивное решение проблемы Flatten. Используя множественную диспетчеризацию Common Lisp Object System, вы можете рекурсивно решить проблему, определив 3 метода для 3 возможных сценариев:

(defmethod flatten ((tree null))
  "Tree is empty list."
  ())
(defmethod flatten ((tree list))
  "Tree is a list."
  (append (flatten (car tree))
          (flatten (cdr tree))))
(defmethod flatten (tree)
  "Tree is something else (atom?)."
  (list tree))

(flatten '(2 ((8) 2 (9 (d (s (((((a))))))))))) ; => (2 8 2 9 D S A)

Это подход, основанный на накоплении. Локальная функция %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)

Я знаю, что этот вопрос действительно старый, но я заметил, что никто не использовал идиому 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. При этом двойная рекурсивная природа reverse-atomize имеет свои собственные ОЗУ.

Этот популярный вопрос имеет только рекурсивные решения (не считая ответа Райнера).

Давайте иметь циклическую версию:

(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))))))