Стандартное имя для сбора коллекций поддеревьев, удовлетворяющих предикату?

Мне пришлось повторно реализовать определенную функцию почти в каждой программе Lisp, которую я когда-либо писал. Поскольку эта функция настолько полезна, она должна была быть реализована ранее. Я ожидаю, что это будет хорошо известно. Возможно, это часть стандартной библиотеки Common Lisp. Как это называется и от какой библиотеки?Стандартное имя для сбора коллекций поддеревьев, удовлетворяющих предикату?

(defun unknown-function (predicate tree) 
    (loop for item in tree 
     if (funcall predicate item) collect item 
     else if (listp item) append (unknown-function predicate item)))

Он спускается по дереву и создает плоский список всех узлов в этом дереве, удовлетворяющих предикату.

источник

2016-04-06 Throwaway Account 3 Million

Обычно задача, которую вы пытаетесь выполнить, решается путем объединения двух разных функций, которые сглаживают дерево и другие, которые фильтруют элементы из этого списка. В Common Lisp нет примитивной функции flatten (но если вы ее найдете в Google, вы найдете множество определений, например, см. [Эту ссылку] (http://stackoverflow.com/questions/2680864/how-to-remove-nested -parentheses-in-lisp)), тогда как для функции фильтра вы можете использовать remove-if или remove-if-not ([manual] (http://www.lispworks.com/documentation/HyperSpec/Body/f_rm_rm.htm # удалить, если)). – Renzo

'flatten' и' remove-if-not' не могли произвести эту функцию, потому что предикат может выбрать подрешители из дерева, в то время как 'flatten' избавится от всех подписок до того, как предикат получит возможность их увидеть. –

Мое первоначальное утверждение неверно из-за тонкости, в которой подсписки проверяются предикатом до того, как они спускаются. Вот оно, для потомков:

Для этого нет стандартного названия. Это всего лишь комбинация сглаживания списка списков и фильтрация элементов, которые не удовлетворяют предикату. В Common Lisp нет встроенного сглаживания, но это будет комбинация вашего собственного flatten, а также стандарт remove-if-not.

Это немного больше общего с subst семейства функций, которые делают проверки поддеревьев в дополнение к листьям. Однако они заменяют отдельные элементы дерева, а не полностью удаляют их. Таким образом, есть что-то общее с subst-if и subst-if-not, но они все еще не совсем идеальны.

источник

2016-04-06 13:06:32

Не совсем. В моей неизвестной функции предикат может выбрать подписи из дерева, но общая функция «сглаживания» избавится от всех подписок до того, как «remove-if-not» получит возможность передать их в предикат. –

О, это * очень * хороший момент! Я думаю, что это имеет немного больше общего с ** subst ** и ** subst-if-not **. Это все еще не совсем идеальное совпадение, но я обновил свой ответ. –

Есть ли что-то в популярной библиотеке? –

Стандартное имя для сбора коллекций поддеревьев, удовлетворяющих предикату?

ответ

Смежные вопросы