最初にキーワードのリストが与えられ、次に別の与えられた単語がリストにあるかどうかを答える必要がある、適度に効率的な「キーワード認識アルゴリズム」を実装したいとします。
命令型言語では、キーワードをツリーに格納します（文字ごとに1つのノード）。次に、テストする単語を受け取ったら、ツリーをスキャンして、その単語がキーワードであるかどうかをテストします。
そのようなアルゴリズムが関数型言語でどのようにコーディングされるのかを理解したいと思います。「命令型」アルゴリズムの効率を維持しながら、「ステートレス」プログラミングの利点をどのように得るのでしょうか。毎回再構築したくない場合は、ルックアップ間のどこかにツリーを保存する必要はありませんか？
つまり、ノードごとの文字だと思います...キーワード検索用の単純なハッシュツリースキームのようなものです。これまたは別の種類のツリーを想定して...（疑似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)
)
これがあなたの言いたいことなら、これはかなり単純な関数型プログラミングです。本当にステートレスですか？それは議論の問題です。関数型プログラミングのいくつかの形式は、通常「状態」と呼ばれるものをスタックに格納すると言う人もいます。さらに、Steeleの本の初版以来、Common LISPには反復構造があり、LISPは長い間setqを持っていました。
しかし、プログラミング言語の理論では、「ステートレス」とは、ここに示す考え方にかなり満足しています。
上記はあなたが言っている配置のようなものだと思います。
ここで説明するように、子のリストを含む木のようなものが必要だと思います。