How can a simple tree algorithm be encoded in a functional language?

Question

Suppose I want to implement a reasonably efficient "keyword recognition algorithm" that first gets a list of keywords and then should respond if there was another given word in the list.

In an imperative language, I would save the keywords in a tree (one node per character). Then, upon receiving the word for verification, I scan my tree to see if this word is a keyword.

I would like to understand how such an algorithm will be encoded in a functional language. How to get the benefits of "stateless" programming, while maintaining the effectiveness of "imperative" algorithms. Don't you need to store the tree somewhere between the searches if you do not want to rebuild it every time?

Answer 1

I think you mean the symbol behind the node ... sort of like a simple hash tree scheme for searching by keywords. Assuming this or even another tree ... imagine something like this (in a 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) ) 

If this is what you mean, this is pretty straightforward functional programming. Is he stateless? This is a matter of debate. Some people will say some forms of functional programming store what we usually call a “state” on the stack. Moreover, Common LISP, even after the first issue of Steele’s book had iterative constructs, and LISP has setq for a long time.

But in the theory of programming languages, what we mean by “stateless” is largely satisfied with the idea presented here.

I think this is something like what you mean.

Answer 2

I assume that you need something like a tree with a list of children, as described here .