Функция Flatten Nests в Лиспе - нужна помощь в понимании

Я пытался найти способ уплотнения вложенных списков в числа, которые возвращаются в исходный список, но у меня возникли некоторые проблемы.

Я смотрел на функцию сглаживания (которая так широко доступна), которая приведена здесь:

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

Я понимаю, что этот пример - рекурсия, но как он работает? Он проверяет, является ли элемент нулевым или атомным, но что он делает, если элемент попадает в эти условия?

Ответы на вопрос(3)

(defun flatten (l)

Выше определяет функциюFLATTEN с одним аргументом под названиемL.

  (cond

ЕСЛ

    ((null l) nil)

значение аргументаL - пустой список, верните пустой список.

    ((atom l) (list l))

или если аргументL является атомом (то есть не списком), затем возвращает список с атомом в качестве единственного элемента.

    (t 

иначе у нас есть непустой список

       (loop for a in l

затем цикл по всем элементам в списке, который является значениемL

        appending (flatten a)

и добавить результаты выравнивания каждого элемента списка.

))))
 Rainer Joswig06 мая 2012 г., 00:24
@ Zchpyvr: APPENDING - это функция макроса LOOP. Lispworks.com / документация / HyperSpec / Кузов / 06_ac.htm
 Zchpyvr06 мая 2012 г., 00:17
Являетсяappending ключевое слово?
Решение Вопроса

В мой день вместо(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 )

Так что сглаживание списка атомов - этоid операция (в 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 )

И так далее, и так далее, для большего количества уровней вложенности.

NILs как элементы в списках создают проблему.NIL - пустой список, и пустой список не содержит ничего, поэтому не должен ничего добавлять. НоNIL тоже атом. Таким образом, мы делаем особый случай для этого, чтобын заключите его в единый список - оставьте все как есть, поэтому при добавлении он просто исчезнет.

 johnbakers14 нояб. 2013 г., 12:33
@ RainerJoswig Что подразумевается подapply не работает над длинным списком? Должны ли все приложенияapply переписать как рекурсивные функции, если списки длинные? и как долго это слишком долго, чтобы использоватьapply?
 Zchpyvr06 мая 2012 г., 00:12
С другими ответами о том, как выполняется код, и с объяснением Уиллом Нессом логики этой программы (которую я бы не понял иначе) я теперь понимаю эту концепцию!
 Rainer Joswig05 мая 2012 г., 23:10
APPLY не очень хорошая идея, поскольку она не работает с произвольно длинными списками.
 Will Ness05 мая 2012 г., 23:11
@ RainerJoswig просто использовал его для иллюстрации.
 Rainer Joswig14 нояб. 2013 г., 13:20
@ OpenLearner:CALL-ARGUMENTS-LIMIT может быть всего 50. ИспользуйтеREDUCE или что-то другое..

nil - это конец списка, верните ноль.

Если элемент, который вы просматриваете, не является списком, возвращайте список, содержащий этот элемент (на самом деле я не уверен, что это правильно, поскольку при наличии атома, который не является списком, он возвращает список с атом, а не сам атом).

Иначе (если это список), переберите все его элементы и добавьте все сплющенные поддеревья (которые вы сгладили, вызвавflatten), затем верните их.

Это короткий, но не самый эффективный алгоритм, так как добавление должно идти до конца списка, чтобы заключить одну часть в хвост другой. Ниже немного более запутанный, но выглядит как более эффективный вариант:

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

Алгоритм этой функции выполняет следующие действия:

Если у нас нет ни первого элемента, ни остального - мы сделали все, поэтому просто вернемсяnil (конец списка).

Если первого элемента нет, разделите второй на первый и остальные и повторите.

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

РЕДАКТИРОВАТЬ Я изменил # 3, потому что интерпретация была очень расплывчатой / могла быть неправильной.

 Will Ness06 мая 2012 г., 09:21
ваш код является линейно-рекурсивным, а не древовидным; но на реализации без TCO% cons (есть ли вообще? ..) это все еще полноценная рекурсия. Плюс, это тоже много значит, заново воссоздавая структуру ввода. Обе проблемы можно исправить за один шаг. Вот один пример как. :)
 Zchpyvr06 мая 2012 г., 00:22
Даже после долгого изучения твоей эффективной функции выравнивания ... Я все еще не понимаю. Я на пороге Lisp, но я вернусь к этому коду в другой день и пойму вашу концепцию. Благодарность
 Will Ness08 мая 2012 г., 07:54
Я думаюmapcan не будет выполнять никаких дополнительных обходов, и я ожидаю, что(loop for a in l nconcing (g a)) чтобы тоже ничего не делать. Максимальная глубина рекурсии для обоих - это глубина вложения, но для вашей версии, которая заменяет зацикливание на рекурсию, это будет длина сглаженного списка. Даже без повторного использования старой структуры (которая имеет свое место, просто следует четко обозначить, например,nflatten name) есть преимущества переписывания кода минусов TCO%, такого как ваш, как Цикл вместо рекурсии, например w /do конструирование, построение списка результатов сверху вниз (чтобы избежатьreverse).
 Will Ness08 мая 2012 г., 10:06
код в вашем ответе прямо сейчас является хвостово-рекурсивным по модулю минусами. Его можно преобразовать в цикл с помощью стандартной методики, создавая список результатов сверху вниз, сохраняя при этом его конечный указатель.loop сnconcing может сделать то же самое, поэтому он будет только пересматривать результат последнего рекурсивного вызоваflatten (а Частичное решение). Для полного решения ваш код может быть переведен в цикл, илиflatten можно переписать, чтобы вернутьlast клетка тоже.
 Will Ness08 мая 2012 г., 16:55
Pastebin.com / smPKTSQN Я тестировал с CLISP 2.38. mapcan был самым быстрым, ваш код ("linear rec") занял 2-е место в 1,3 раза, цикл сверху вниз - в 1,4 раза, затем nconcing - в 1,6 раза, а добавление было последним, в 2,5 раза медленнее. nconcing явно делает что-то лучше, работает в 1,5 раза быстрее, чем добавление. Очень интересно посмотреть, что это будет с твоей стороны. На чем вы это тестируете? Пожалуйста, проверьте этот код как есть, так что мы можем сравнить. Кстати, «линейная запись» и «добавление» работают с худшими cmpxties по сравнению с тремя другими для увеличения размера данных.

Ваш ответ на вопрос