SICP练习3.17的一点疑问和思考

win_hate

你上面只给出了一部分代码吧？看得不是很明白，好像是把访问过的放到一个表格里然后通过函数参数来传递。

你说的这个问题我了解不多，下面是一些粗浅的看法。

纯函式风格不用 set!，可以用生成新的值来取代旧的值。比如现在有一棵树，插人一个节点在命令式风格的语言中可以通过赋值实现，而在函式风格的语言里可以通过生成一棵新树来实现（但我不清楚高效生成的细节，新旧对象应该共享了大部分内容）。我对 3.17 的解答是通过 hash 表实现的，按这个思路，只要在每次修改 hash 表的时候都重新生成一个表就行了。这个跟用参数传递修改过的值是很类似的。

比如我现在有一个表 A = (1 2 3 4)，那么 (cons 5 (cdr (cdr A))) 就得到了一个新的表 (5 3 4)。

[ 本帖最后由 win_hate 于 2009-3-14 21:40 编辑 ]

win_hate

建议两个参考资料：

[1]    Algorithms - A Functional Programming Approach. F Rabhi - G Lapalme (1999)
[2]    Purely Functional Data Structures.  Okasaki.

第一本用 haskell 实现了常见的数据结构，包括 avl 树。注意到命令式语言实现树要用很多赋值，而 haskell 是纯函式的，看完这本书应该就能解答你的疑惑。

第二本比第一本深，它是 Okasaki 的博士论文。此书讨论了选择恰当的数据结构来适应纯函式语言（比如斜堆，二叉堆），使用的语言为 ML。

[ 本帖最后由 win_hate 于 2009-3-14 21:41 编辑 ]