Chinaunix

标题: SICP练习3.17的一点疑问和思考 [打印本页]

作者: PeterGhostWolf 时间: 2009-03-14 16:40
标题: SICP练习3.17的一点疑问和思考
版主给出的答案是一个使用了set!的代码很简洁的版本。
今天我做到这题时,想把它设计成一个数学函数式的过程.所以就有了如下版本

(define (count-pairs x)
(define (iter x visited)
(cond ((not (pair? x)) (cons 0 visited))
((init x visited) (cons 0 visited))
(else (let ((car-answer (iter (car x) (cons x visited))))
(let ((cdr-answer (iter (cdr x) (cdr car-answer))))
(cons (+ (car car-answer)
(car cdr-answer)
1)
(cdr cdr-answer)))))))
(car (iter x '())))

复制代码

自感丑陋无比,但是又一时没有想出什么好的设计方法(在不使用set!的前提下).
为了保证程序的纯粹数学性真的要牺牲掉这么多吗?

作者: win_hate 时间: 2009-03-14 20:55
你上面只给出了一部分代码吧？看得不是很明白，好像是把访问过的放到一个表格里然后通过函数参数来传递。

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

纯函式风格不用 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 时间: 2009-03-14 21:05
建议两个参考资料：

[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 编辑 ]

作者: PeterGhostWolf 时间: 2009-03-14 23:36
唔...我少帖了init的定义,就是简单地判断x是否是队列y的一个元素...
谢谢版主推荐的资料!我去找来读.

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)