Wie kann ein einfacher Baumalgorithmus in einer funktionalen Sprache codiert werden?

Question

Angenommen, ich möchte einen einigermaßen effizienten „Schlüsselworterkennungsalgorithmus“ implementieren, dem zunächst eine Liste mit Schlüsselwörtern gegeben wird und der dann antworten muss, wenn ein anderes gegebenes Wort in der Liste enthalten ist.

In einer imperativen Sprache würde ich die Schlüsselwörter in einem Baum speichern (ein Knoten pro Zeichen).Wenn ich dann ein Wort zum Testen erhielt, scannte ich meinen Baum, um zu testen, ob es sich bei dem Wort um ein Schlüsselwort handelt.

Ich würde gerne verstehen, wie ein solcher Algorithmus in einer funktionalen Sprache codiert werden würde.Wie kann man die Vorteile der „zustandslosen“ Programmierung nutzen und gleichzeitig die Effizienz „imperativer“ Algorithmen beibehalten?Ist es nicht notwendig, den Baum irgendwo zwischen den Suchvorgängen zu speichern, wenn Sie ihn nicht jedes Mal neu erstellen möchten?

Answer 1

Ich denke, was Sie meinen, ist ein Zeichen pro Knoten ...So etwas wie ein einfaches Hash-Baum-Schema für die Schlüsselwortsuche.Angenommen, diese oder sogar eine andere Baumart ...Stellen Sie sich vor, Sie machen so etwas (in Pseudo-LISP):

(defun buildtree (wordlist) ...code to build tree recursively returns the tree...)
(define lookup (tree word) ...code to look up word using tree, returns t or nil...)

(defun lookupmany (tree querylist)
   (if (eq querylist nil)
       nil
       (cons (lookup tree (car querylist)) (lookupmany tree (cdr querylist))
   )
)

(defun main (wordlist querylist) ; the main entry point
   (lookupmany (buildtree wordlist) querylist)
)

Wenn Sie das meinen, handelt es sich um eine ziemlich einfache funktionale Programmierung.Ist es wirklich staatenlos?Das ist eine Frage der Debatte.Einige Leute würden einige Formen des funktionalen Programmiers sagen, was wir normalerweise als "Zustand" auf dem Stapel bezeichnen.Darüber hinaus hat Common Lisp, auch seit der ersten Ausgabe des Steele -Buches iterative Konstrukte, und Lisp hat seit langem SetQ.

Aber in der Theorie der Programmiersprachen wird das, was wir unter „zustandslos“ verstehen, durch die hier gezeigte Idee weitgehend erfüllt.

Ich denke, das obige ist in etwa die Vereinbarung, die Sie meinen.

Answer 2

Ich kann mir vorstellen, dass Sie so etwas wie einen Baum mit einer Liste von Kindern wünschen würden, wie beschrieben Hier.