Come si può codificare un semplice algoritmo ad albero in un linguaggio funzionale?

Question

Supponiamo che io voglia implementare un "algoritmo di riconoscimento delle parole chiave" ragionevolmente efficiente, a cui viene prima fornito un elenco di parole chiave e poi devo rispondere se un'altra parola data era nell'elenco.

In un linguaggio imperativo, memorizzerei le parole chiave in un albero (un nodo per carattere).Quindi, quando ricevo una parola da testare, eseguo la scansione del mio albero per verificare se la parola è una parola chiave.

Mi piacerebbe capire come un simile algoritmo verrebbe codificato in un linguaggio funzionale.Come si possono ottenere i vantaggi della programmazione "senza stato" mantenendo l'efficienza degli algoritmi "imperativi".Non è necessario memorizzare l'albero da qualche parte tra le ricerche se non si desidera ricostruirlo ogni volta?

Answer 1

Penso che quello che intendi sia un carattere per nodo...una sorta di semplice schema di albero hash per la ricerca di parole chiave.Supponendo che questo o anche un altro tipo di albero...immagina di fare qualcosa del genere (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)
)

se questo è ciò che intendi, si tratta di una programmazione funzionale abbastanza semplice.È davvero apolide?Questa è una questione di dibattito.Alcune persone direbbero che alcune forme di programmazione funzionale archiviano ciò che normalmente chiamiamo "stato" sullo stack.Inoltre, LISP comune anche dalla prima edizione del libro Steele ha avuto costrutti iterativi e Lisp ha avuto setQ per molto, molto tempo.

Ma nella teoria dei linguaggi di programmazione, ciò che intendiamo per "senza stato" è più o meno soddisfatto dall'idea qui mostrata.

Penso che quanto sopra sia qualcosa di simile alla disposizione che intendi.

Answer 2

Immagino che vorresti qualcosa come un albero con un elenco di bambini, come descritto Qui.