¿Cómo se puede codificar un algoritmo de árbol simple en un lenguaje funcional?

Question

Supongamos que quiero implementar un 'algoritmo de reconocimiento de palabras clave' razonablemente eficiente, al que primero se le proporciona una lista de palabras clave y luego debo responder si otra palabra determinada estaba en la lista.

En un lenguaje imperativo, almacenaría las palabras clave en un árbol (un nodo por carácter).Luego, cuando recibía una palabra para probar, escaneaba mi árbol para comprobar si la palabra es una palabra clave.

Me gustaría entender cómo se codificaría dicho algoritmo en un lenguaje funcional.¿Cómo se pueden obtener los beneficios de la programación "sin estado" manteniendo al mismo tiempo la eficiencia de los algoritmos "imperativos"?¿No es necesario almacenar el árbol en algún lugar entre las búsquedas si no desea reconstruirlo cada vez?

Answer 1

Creo que lo que quieres decir es un carácter por nodo...algo así como un esquema de árbol hash simple para la búsqueda de palabras clave.Suponiendo este o incluso otro tipo de árbol...imagina hacer algo como esto (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 esto es lo que quiere decir, se trata de una programación funcional bastante sencilla.¿Es realmente apátrida?Ésa es una cuestión de debate.Algunas personas dirían que algunas formas de programación funcional almacenan lo que normalmente llamamos "estado" en la pila.Además, Common Lisp, incluso desde la primera edición del libro Steele, ha tenido construcciones iterativas, y Lisp ha tenido SETQ durante mucho, mucho tiempo.

Pero en la teoría de los lenguajes de programación, lo que entendemos por "sin estado" queda bastante satisfecho con la idea que se muestra aquí.

Creo que lo anterior es algo así como el arreglo al que te refieres.

Answer 2

Me imagino que querrías algo como un árbol con una lista de niños, como se describe aquí.