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

Question

Suppose I want to implement a reasonably efficient 'keyword recognition algorithm', that is first given a list of keyword, and must then answer if another given word was in the list.

In an imperative language, I would store the keywords in a tree (one node per character). Then, when receiving a word to test, I would scan my tree to test if the word is a keyword.

I'd like to understand how such an algorithm would be coded in a functional language. How does one get the benefits of 'stateless' programming while keeping the efficiency of 'imperative' algorithms. Isn't it necessary to store the tree somewhere between the lookups if you don't want to rebuild it each time?

Answer 1

I imagine you'd want something like a tree with a list of children, as described here.

Answer 2

I think what you mean is a character per node... sort of like a simple hash tree scheme for keyword lookup. Assuming this or even another kind of tree... imagine doing something like this (in 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 fairly straight-forward functional programming. Is it really stateless? That's a matter of debate. Some people would say some forms of functional programming store what we normally call "state" on the stack. Moreover, Common LISP even since the first edition of the Steele book has had iterative constructs, and LISP has had setq for a long, long time.

But in the theory of programming languages, what we mean by "stateless" is pretty much satisfied by the idea shown here.

I think the above is something like the arrangement you mean.