如何用函数式语言编写简单的树算法?
-
09-06-2019 - |
题
假设我想实现一个相当有效的“关键字识别算法”,首先给出一个关键字列表,然后必须回答列表中是否有另一个给定的单词。
在命令式语言中,我会将关键字存储在树中(每个字符一个节点)。然后,当收到要测试的单词时,我会扫描我的树以测试该单词是否是关键字。
我想了解如何用函数语言编码这样的算法。如何在保持“命令式”算法的效率的同时获得“无状态”编程的好处。如果您不想每次都重建树,是否有必要将树存储在查找之间的某个位置?
解决方案
我认为你的意思是每个节点一个字符......有点像用于关键字查找的简单哈希树方案。假设这种树甚至另一种树......想象一下做这样的事情(在伪 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书的第一版具有迭代构造,LISP的常见LISP和LISP已经有很长时间了。
但在编程语言理论中,我们所说的“无状态”几乎可以通过这里展示的想法得到满足。
我觉得上面的安排和你说的差不多。
其他提示
我想你会想要一棵树之类的东西,上面有孩子的名单,如上所述 这里.
不隶属于 StackOverflow