単純なツリー アルゴリズムを関数型言語でコーディングするにはどうすればよいでしょうか?

Question

かなり効率的な「キーワード認識アルゴリズム」を実装したいとします。これは、最初にキーワードのリストが与えられ、次に、別の与えられた単語がリスト内にあるかどうかを答える必要があります。

命令型言語では、キーワードをツリー (文字ごとに 1 つのノード) に保存します。次に、テストする単語を受け取ったら、ツリーをスキャンしてその単語がキーワードかどうかをテストします。

このようなアルゴリズムが関数型言語でどのようにコーディングされるのかを理解したいと考えています。「命令型」アルゴリズムの効率を維持しながら、「ステートレス」プログラミングの利点を得るにはどうすればよいでしょうか。毎回ツリーを再構築したくない場合は、ルックアップ間のどこかにツリーを保存する必要があるのではないでしょうか?

Answer 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 Bookの初版が反復的な構成要素を持っていて以来、Lispは長い間SetQを持っていました。

しかし、プログラミング言語の理論では、「ステートレス」が意味するものは、ここで示した考え方によってほぼ満たされます。

以上がおっしゃるような整理かと思います。

Answer 2

説明されているように、子のリストを含むツリーのようなものが必要になると思います。 ここ.