Comment un simple algorithme d'arbre de être codée dans un langage fonctionnel?

Question

Supposons que je veuille mettre en œuvre un raisonnablement efficace "mot algorithme de reconnaissance", c'est d'abord donné une liste de mots-clés, et doit ensuite répondre si un mot donné est dans la liste.

Dans un langage impératif, je voudrais stocker les mots-clés dans un arbre (un nœud par caractère).Puis, lors de la réception d'un mot pour le tester, je voudrais scan de mon arbre pour tester si le mot est un mot-clé.

J'aimerais comprendre comment un tel algorithme serait codée dans un langage fonctionnel.Comment peut-on obtenir les avantages de la "apatride" programmation tout en conservant l'efficacité de 'impératif' algorithmes.N'est-il pas nécessaire de stocker l'arbre quelque part entre les recherches si vous ne voulez pas de le reconstruire à chaque fois?

Answer 1

Je pense que ce que tu veux dire, c'est un personnage par nœud...un peu comme un simple arbre de hachage régime pour le mot-clé de recherche.En supposant que ce ou même un autre type d'arbre...imaginer faire quelque chose comme ceci (en 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)
)

si c'est ce que tu veux dire, c'est assez simple en programmation fonctionnelle.Est-il vraiment apatride?C'est un sujet de débat.Certaines personnes diront certains les formes de la programmation fonctionnelle stocker ce que nous appelons généralement "état" sur la pile.En outre, Common LISP, même depuis la première édition de l'Steele livre a eu itératif constructions, et de LISP a eu setq pour un long, long temps.

Mais dans la théorie des langages de programmation, ce que nous entendons par "apatride" est à peu près convaincu par l'idée présentée ici.

Je pense que le ci-dessus est quelque chose comme l'arrangement que vous voulez dire.

Answer 2

J'imagine que vous voulez quelque chose comme un arbre avec une liste d'enfants, comme décrit ici.