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

Question

Angenommen, ich möchte einen einigermaßen effizienten Schlüsselworterkennungsalgorithmus implementieren, der zuerst eine Liste mit Schlüsselwörtern erhält und dann antworten muss, ob ein anderes gegebenes Wort in der Liste enthalten ist.

In einer imperativen Sprache würde ich die Schlüsselwörter in einem Baum (ein Knoten pro Zeichen) speichern. Wenn ich dann ein zu testendes Wort erhalte, scanne ich meinen Baum, um zu testen, ob das Wort ein Schlüsselwort ist.

Ich würde gerne verstehen, wie ein solcher Algorithmus in einer funktionalen Sprache codiert wäre. Wie erhält man die Vorteile der "zustandslosen" Programmierung, während die Effizienz von "imperativen" Algorithmen erhalten bleibt? Ist es nicht notwendig, den Baum irgendwo zwischen den Suchvorgängen zu speichern, wenn Sie ihn nicht jedes Mal neu erstellen wollen?

Answer 1

Ich denke, was du meinst, ist ein Zeichen pro Knoten ... eine Art wie ein einfaches Hash-Baum-Schema für Keyword-Lookup. Unter der Annahme, dies oder sogar ein andere Art von Baum ... vorstellen, so etwas wie dies zu tun (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 dies ist, was du meinst, das ist ziemlich geradlinig funktionale Programmierung. Ist es wirklich staatenlos? Das ist eine Frage der Debatte. Manche Leute würden sagen, einige Formen von funktionaler Programmierung speichern, was wir normalerweise "Zustand" auf dem Stapel nennen. Darüber hinaus hat Common LISP bereits seit der ersten Ausgabe des Steele-Buchs iterative Konstrukte, und LISP hatte Setq für eine lange, lange Zeit.

Aber in der Theorie der Programmiersprachen ist das, was wir mit "staatenlos" meinen, ziemlich zufrieden mit der hier gezeigten Idee.

Ich denke, das oben genannte ist so etwas wie die Anordnung, die Sie meinen.

Answer 2

Ich stelle mir vor, Sie möchten etwas wie einen Baum mit einer Liste von Kindern, wie beschrieben here.