algorithm - 如何用函数式语言编写简单的树算法？

Question

假设我想实现一个相当有效的“关键字识别算法”，首先给定一个关键字列表，然后必须回答列表中是否有另一个给定的单词。

在命令式语言中，我会将关键字存储在树中(每个字符一个节点)。然后，当收到要测试的词时，我会扫描我的树以测试该词是否是关键字。

我想了解如何使用函数式语言编写此类算法。如何在保持“命令式”算法效率的同时获得“无状态”编程的好处。如果您不想每次都重建它，是否有必要将树存储在查找之间的某个位置？

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)
)

如果这就是您的意思，那么这就是相当简单的函数式编程。 真的是无国籍吗？这是一个有争议的问题。有些人会说一些 函数式编程的形式在堆栈上存储我们通常所说的“状态”。 此外，Common LISP 甚至从 Steele 书的第一版开始就有迭代 构造，LISP 已经有 setq 很长很长时间了。

但是在编程语言的理论中，我们所说的“无状态”已经非常满足这里展示的想法。

我觉得上面的就是你说的那种安排。