Comment un algorithme d'arborescence simple peut-il être codé dans un langage fonctionnel?

Question

Supposons que je souhaite implémenter un «algorithme de reconnaissance de mots-clés» raisonnablement efficace, auquel on donne d'abord une liste de mots-clés, et qui doit ensuite répondre si un autre mot figurait dans la liste.

Dans un langage impératif, je stockerais les mots-clés dans un arbre (un nœud par caractère). Puis, en recevant un mot à tester, je voudrais scanner mon arbre pour tester si le mot est un mot-clé.

Je voudrais comprendre comment un tel algorithme serait codé dans un langage fonctionnel. Comment obtenir les avantages de la programmation «sans état» tout en conservant l'efficacité des algorithmes «impératifs»? N'est-il pas nécessaire de stocker l'arbre quelque part entre les recherches si vous ne voulez pas le reconstruire à chaque fois?

Answer 1

Je pense que ce que vous voulez dire est un caractère par nœud ... un peu comme un schéma simple d'arbre de hachage pour la recherche par mot clé. En supposant que cela, ou même une autre sorte d'arbre ... imaginez faire quelque chose comme ça (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 vous voulez dire, cela est assez programmation fonctionnelle simple. Est-ce vraiment apatride? C'est un sujet de débat. Certaines personnes diraient certaines formes de magasin de programmation fonctionnelle ce que nous appelons normalement "état" sur la pile. De plus, Common LISP, même depuis la première édition du livre de Steele a eu des constructions itératives , et LISP a eu setq depuis longtemps. Mais dans la théorie des langages de programmation, ce que nous entendons par "sans état" est à peu près satisfait par l'idée présentée ici. Je pense que ce qui précède 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 here.