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

Question

Как я могу рекурсивно удалить вложенные скобки в 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)

Спасибо

Answer 1

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

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

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

Answer 2

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

Answer 3

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

Answer 4

(defun flatten (l)
  (cond ((null l) nil)
        ((atom (car l)) (cons (car l) (flatten (cdr l))))
        (t (append (flatten (car l)) (flatten (cdr l))))))

Answer 5

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

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

Answer 6

Я знаю, что этот вопрос действительно старый , но я заметил, что никто не использовал идиому 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 имеет свои собственные RAM идификаций.

Answer 7

Это аккумуляторный подход. Локальная функция % flatten хранит аккумулятор хвоста (часть списка right , которая уже сглажена). Когда часть, оставшаяся для выравнивания (часть списка left ) пуста, возвращается хвост. Когда подлежащая выравниванию часть не является списком, она возвращает эту часть с префиксом на хвосте. Когда часть, подлежащая выравниванию, является списком, она выравнивает rest списка (с текущим хвостом), а затем использует этот результат в качестве хвоста для выравнивания первой части списка.

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

Answer 8

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

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

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

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

Answer 9

(defun unnest (somewhat)
  (cond
   ((null somewhat) nil)
   ((atom somewhat) (list somewhat))
   (t
    (append (unnest (car somewhat)) (unnest (cdr somewhat))))))