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

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

我想了解如何用功能语言对这种算法进行编码。如何在保持"命令式"算法效率的同时获得"无状态"编程的好处。如果我们不想每次都重建树，是否有必要将树存储在查找之间的某个位置？

解决方案

回答

我想我们会想要像带有孩子列表的树一样的东西，如此处所述。

回答

我认为意思是每个节点一个字符...有点像用于关键字查找的简单哈希树方案。假设这棵树或者什至另一种树……假设做这样的事情(在伪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甚至自斯蒂尔书的第一版以来就具有迭代性
构造，并且LISP已经使用setq很长时间了。

但是，在编程语言理论中，这里显示的思想使我们对"无状态"的含义非常满意。

我认为上述情况与意思很像。