Standardname für Funktion, die Unterbäume sammelt, die ein Prädikat erfüllen?

Ich musste eine bestimmte Funktion in so ziemlich jedem Lisp-Programm neu implementieren, das ich je geschrieben habe. Da diese Funktion so nützlich ist, muss sie vorher implementiert worden sein. Ich würde erwarten, dass es gut bekannt ist. Vielleicht ist es Teil der Standardbibliothek von Common Lisp. Wie heißt es und aus welcher Bibliothek stammt es?Standardname für Funktion, die Unterbäume sammelt, die ein Prädikat erfüllen?

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

Es senkt sich durch einen Baum und schafft eine flache Liste aller Knoten in diesem Baum, der das Prädikat erfüllen.

Quelle

2016-04-06 Throwaway Account 3 Million

Normalerweise wird die Aufgabe, die Sie ausführen möchten, gelöst, indem zwei verschiedene Funktionen kombiniert werden: eine, die einen Baum flach macht, und eine andere, die Elemente aus dieser Liste filtert. In Common Lisp gibt es keine flatten Primitive Funktion (aber wenn Sie es googlen finden Sie viele Definitionen, zum Beispiel siehe [this link] (http://stackoverflow.com/questions/2680864/how-to-remove-nested (parentheses-in-lisp)), während für die Filterfunktion remove-if oder remove-if-not verwendet werden kann ([manual] (http://www.lispworks.com/documentation/HyperSpec/Body/f_rm_rm.htm) # remove-if)). – Renzo

'flatten' und' remove-if-not' konnten diese Funktion nicht erzeugen, da das Prädikat Sublisten aus dem Baum auswählen kann, während 'flatten' alle Unterlisten löscht, bevor das Prädikat eine Chance bekommt, sie zu sehen. –

Meine ursprüngliche Aussage ist falsch, wegen der Subtilität, in der die Unterlisten durch das Prädikat geprüft werden, bevor sie hinuntergestiegen werden. Hier ist es für die Nachwelt:

Es gibt keinen Standardnamen dafür. Es ist nur eine Kombination aus dem Reduzieren einer Liste von Listen und dem Herausfiltern der Elemente, die ein Prädikat nicht erfüllen. In Common Lisp gibt es keine eingebaute Flatten, aber es wäre eine Kombination aus flatten und dem Standard remove-if-not.

Das hat ein bisschen mehr gemeinsam mit subst Familie von Funktionen, die die Teilbäume zusätzlich zu den Blättern zu tun überprüfen. Sie ersetzen jedoch einzelne Elemente des Baums, anstatt sie vollständig zu entfernen. Es gibt also etwas gemeinsam mit subst-wenn und subst-wenn-nicht, aber sie sind immer noch nicht ganz perfekte Übereinstimmungen.

Quelle

2016-04-06 13:06:32

Nicht genau. In meiner unknown-Funktion kann das Prädikat Sublisten aus dem Baum auswählen, aber eine generische 'flatten'-Funktion würde alle Unterlisten loswerden, bevor' remove-if-not' eine Chance erhält, sie an das Prädikat zu übergeben. –

Oh, das ist ein * sehr * schöner Punkt! Das hat mit ** subst ** und ** subst-if-not ** etwas mehr gemeinsam, denke ich. Es ist immer noch keine perfekte Übereinstimmung, aber ich habe meine Antwort aktualisiert. –

Gibt es sowas in einer beliebten Bibliothek? –

Standardname für Funktion, die Unterbäume sammelt, die ein Prädikat erfüllen?

Antwort

Verwandte Themen