Como um algoritmo de árvore simples pode ser codificado em uma linguagem funcional?

Question

Suponha que eu queira implementar um 'algoritmo de reconhecimento de palavras-chave' razoavelmente eficiente, que primeiro recebe uma lista de palavras-chave e deve então responder se outra palavra estiver na lista.

Em uma linguagem imperativa, eu armazenaria as palavras-chave em uma árvore (um nó por caractere).Então, ao receber uma palavra para testar, eu examinaria minha árvore para testar se a palavra é uma palavra-chave.

Gostaria de entender como tal algoritmo seria codificado em uma linguagem funcional.Como obter os benefícios da programação 'sem estado' e, ao mesmo tempo, manter a eficiência dos algoritmos 'imperativos'?Não é necessário armazenar a árvore em algum lugar entre as pesquisas se você não quiser reconstruí-la todas as vezes?

Answer 1

Acho que o que você quer dizer é um caractere por nó ...uma espécie de esquema de árvore hash simples para pesquisa de palavras-chave.Supondo que este ou mesmo outro tipo de árvore...imagine fazer algo assim (em 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 é isso que você quer dizer, esta é uma programação funcional bastante direta.É realmente apátrida?Isso é uma questão de debate.Algumas pessoas diriam algumas formas de programação funcional armazenam o que normalmente chamamos de "estado" na pilha.Além disso, o Common Lisp, mesmo desde a primeira edição do Steele Book, teve construções iterativas, e o LISP teve o SetQ há muito tempo.

Mas na teoria das linguagens de programação, o que queremos dizer com “sem estado” é bastante satisfeito pela ideia mostrada aqui.

Acho que o que foi dito acima é algo parecido com o arranjo que você quer dizer.

Answer 2

Imagino que você queira algo como uma árvore com uma lista de filhos, conforme descrito aqui.