Standard name for function collecting subtrees satisfying a predicate?

Question

I've had to re-implement a particular function in pretty much every Lisp program I've ever written. Since this function is so useful, it must have been implemented before. I'd expect it to be well known. Perhaps it is part of Common Lisp's standard library. What is it called and what library is it from?

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

It descends through a tree and creates a flat list of all the nodes in that tree that satisfy the predicate.

Usually the task that you are trying to perform is solved by combining two different functions, one that flatten a tree and another one that filter elements from that list. In Common Lisp there is no flatten primitive function (but if you google it you will find a lot of definitions, for instance see [this link](http://stackoverflow.com/questions/2680864/how-to-remove-nested-parentheses-in-lisp)), while for the filter function you could use remove-if or remove-if-not ([manual](http://www.lispworks.com/documentation/HyperSpec/Body/f_rm_rm.htm#remove-if)). — Renzo, Apr 06 '16 at 06:12
`flatten` and `remove-if-not` couldn't produce this function, because the predicate can select sublists from the tree, while `flatten` would get rid of all sublists before the predicate gets a chance to see them. — Throw Away Account, Apr 06 '16 at 13:09

Joshua Taylor · Accepted Answer · 2016-04-06T13:18:11.790

0

My original statement is wrong, because of the subtlety wherein the sublists are tested by the predicate before they are descended into. Here it is, for posterity:

There's no standard name for this. It's just a combination of flattening a list of lists and filtering out the elements that don't satisfy a predicate. In Common Lisp, there's no built-in flatten, but it would be a combination of your own flatten, and the standard remove-if-not.

This has a bit more in common with subst family of functions which do check the subtrees in addition to the leaves. However, they're replacing individuals elements of the tree, rather than removing them completely. So there's something in common with subst-if and subst-if-not, but they're still not quite perfect matches.

edited Apr 06 '16 at 13:18

answered Apr 06 '16 at 13:06

Joshua Taylor

84,998
9
154
353

1

Not exactly. In my unknown-function, the predicate can select sublists from the tree, but a generic `flatten` function would get rid of all sublists before `remove-if-not` gets a chance to pass them to the predicate. – Throw Away Account Apr 06 '16 at 13:12
Oh, that's a *very* nice point! This has a bit more in common with **subst** and **subst-if-not**, I think. It's still not quite a perfect match, but I've updated my answer. – Joshua Taylor Apr 06 '16 at 13:14
Is there something like it in a popular library? – Throw Away Account Apr 06 '16 at 13:22
Something like what? – Joshua Taylor Apr 06 '16 at 13:22
Something like the `unknown-function` from my question. – Throw Away Account Apr 06 '16 at 13:27
Not that I know of. That part of the answer still stands (as far as I know): there's no standard name for this. – Joshua Taylor Apr 06 '16 at 13:28
Thanks for clarifying. I had interpreted "standard" as referring to the ANSI standard. – Throw Away Account Apr 06 '16 at 13:31
@cat What is known as filter in the other languages? **remove-if-not** could be known as filter, but **subst** isn't filter, and OP's original function isn't filter. – Joshua Taylor Apr 07 '16 at 12:52

Standard name for function collecting subtrees satisfying a predicate?

1 Answers1