程序员人生 网站导航

SICP 习题 (2.4) 解题总结

栏目:互联网时间:2014-10-06 08:00:00

SICP 习题 2.4 是一道很有意思的题目,它在一定程度上会改变你对数据结构的认识。

按题目的说法,这里讲到的是“序对的过程性表示”。


序对大家应该熟悉了,前面几道题都和序对有关系,那序对的“过程性表示”是什么意思呢?

简单一点说就是用一种过程(或者说函数啦)来实现序对。


在此之前,对于很多程序员来讲,数据是数据,过程是过程,两者是单独存在的,过程一般是用来访问数据的。像这里讲到的使用一个过程来实现数据结构真是一件奇怪的事情。


先看看题目给出的样例吧,题目说到,如果我们有下面这些个过程定义,那么,对于任意的x 和y , (car(cons x y))都将产生x:


(define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p)))


上面的代码阅读起来还是有些困难的,因为涉及到两个lambda过程

就像题目说到的,为了更好地理解这里的过程,建议使用代换的方式,我们来看看代换的过程:


(car(cons x y))

=> (car (lambda (m) (m x y)))

=> ((lambda (m) (m x y)) (lambda (p q) p))

=> ((lambda (p q) p) x y)

=>((lambda (x y) x))

=> x


我第一次做完这个代换过程后都觉得不可思议,感觉就像是眼睁睁看着扑克牌从刘谦手里消失一样。


这里cons返回的是一个lambda函数,这个lambda函数接受一个参数,将这个参数作用于x y。

而car 接受一个参数,将这个参数作用于另一个lambda函数,这个lambda函数接受两个参数,永远返回第一个参数。

将cons和car连接起来使用就是“作用于x y,永远返回第一个参数x”。


这个想明白了以后完成题目就比较简单了,题目要求我们按这个思路去定义对应cdr过程,我定义的cdr代码如下:

(define (cdr z) (z (lambda (p q) q)))

意思就是cdr接受一个参数,将这个参数作用于一个lambda过程,该lambda过程接受两个参数,永远返回第二个参数。


这样题目就完成了,不过关于这道题给我们带来的启发还是值得我们仔细琢磨。


完成题目容易,理解题目的用意不易。。。。。。


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐