简单树算法如何用功能语言编码？

假设我想实现一个合理有效的“关键字识别算法”，它首先给出关键字列表，然后必须回答列表中是否有其他给定单词。简单树算法如何用功能语言编码？

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

我想了解如何将这种算法编码为功能语言。如何在保持'命令式'算法效率的同时获得'无状态'编程的好处。如果你不想每次都重建它，那么是否有必要将树存储在查找之间的某处？

2008-09-05 Xavier Nodet

我想你的意思是每个节点上的字符......有点像关键字查找的简单哈希树方案。假设这甚至是另一种树......想象做这样的事情（在伪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。

但是在编程语言理论中，我们所说的“无状态”的意思是非常满意的。

我认为上面的东西就像你的意思。

来源

2008-09-05 22:26:38

我想你会想要像树一样的儿童列表，如here所述。

来源

2008-09-05 21:37:58

简单树算法如何用功能语言编码？

回答

相关问题