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

2

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

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

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

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

Ваш Ответ

3   ответа
3

В мой день вместо(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 тоже атом. Таким образом, мы делаем особый случай для этого, чтобын заключите его в единый список - оставьте все как есть, поэтому при добавлении он просто исчезнет.

APPLY не очень хорошая идея, поскольку она не работает с произвольно длинными списками. Rainer Joswig
@ RainerJoswig просто использовал его для иллюстрации. Will Ness
С другими ответами о том, как выполняется код, и с объяснением Уиллом Нессом логики этой программы (которую я бы не понял иначе) я теперь понимаю эту концепцию! Zchpyvr
@ OpenLearner:CALL-ARGUMENTS-LIMIT может быть всего 50. ИспользуйтеREDUCE или что-то другое.. Rainer Joswig
@ RainerJoswig Что подразумевается подapply не работает над длинным списком? Должны ли все приложенияapply переписать как рекурсивные функции, если списки длинные? и как долго это слишком долго, чтобы использоватьapply? johnbakers
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)

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

))))
Являетсяappending ключевое слово? Zchpyvr
@ Zchpyvr: APPENDING - это функция макроса LOOP. Lispworks.com / документация / HyperSpec / Кузов / 06_ac.htm Rainer Joswig
2

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, потому что интерпретация была очень расплывчатой / могла быть неправильной.

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

Похожие вопросы