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

PeterGhostWolf

版主给出的答案是一个使用了set!的代码很简洁的版本。
今天我做到这题时,想把它设计成一个数学函数式的过程.所以就有了如下版本

1. 
   
2. (define (count-pairs x)
   
3.   (define (iter x visited)
   
4.     (cond ((not (pair? x)) (cons 0 visited))
   
5.           ((init x visited) (cons 0 visited))
   
6.           (else (let ((car-answer (iter (car x) (cons x visited))))
   
7.                   (let ((cdr-answer (iter (cdr x) (cdr car-answer))))
   
8.                     (cons (+ (car car-answer)
   
9.                              (car cdr-answer)
   
10.                              1)
    
11.                           (cdr cdr-answer)))))))
    
12.   (car (iter x '())))
    

复制代码

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

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

PeterGhostWolf

唔...我少帖了init的定义,就是简单地判断x是否是队列y的一个元素...
谢谢版主推荐的资料!我去找来读.