scheme对树的映射

这一节对之前提到的map概念又进行了扩展，map与递归的结合是一种处理树的强有力抽象。
练习2.30 请定义一个与练习2.21中square-list过程类似的square-tree过程。要求定义一个传统过程和一个使用map的过程。

点击查看代码

(define nil '())
(define (square x) (* x x))
;传统做法
(define (square-tree square items)
    (cond ((null? items) nil)
          ((not (pair? items))(square items))
          (else (cons (square-tree square (car items))
                      (square-tree square (cdr items))))))
;使用map的过程
(define (square-tree items)
    (map (lambda (i)
            (if (pair? i)
                (square-tree i)
                (square i)))
                items))

练习2.31 将你在练习2.30做出的解答进一步抽象，做出一个抽象，使它的性质能以下面形式定义square-tree：
做一个抽象过程，使用map的过程可以将square这个算术式替换成任意算法

点击查看代码

(define (algori-tree tree)
    (map (lambda(i)
            (if (pair? i)
                (algori-tree i)
                (algori i)))
                tree))

练习2.32 我们可以将一个集合表示为一个元素互不相互的表，因此就可以将一个集合的所有子集表示为表的表。例如，假定集合为(1 2 3)，它的所有子集的集合就是（（）（3）（2）（2 3）（1）（1 3）（1 2）（1 2 3））。请完成下面的过程定义，它生成出一个集合的所有子集的集合。并解释它为什么能完成这一工作。

这道题很有意思。
关于这个集合的问题，可以联想到第一章里那个找零钱的问题，那个找零问题的核心思想就是找钱方式的集合为（完全不用第一种钱币的找钱方式）加上（一定使用了第一种钱币的找钱方式的）
放在集合里，就是（除去第一个元素后使用所有元素构成的子集）加上（一定使用了第一种元素的子集）的集合。
观察题目给的代码片段：
(define (subsets s)
(if (null? s)
(list nil)
(let ((rest (subsets (cdr s))))
(append rest (map (body)) rest )))))
其中rest就是除了第一种元素以外的集合
那么很显然，body里面要填写的就是一定包含第一种元素集合
那么怎么实现一定包含第一种元素的集合呢？
很简单，就是在不含第一种元素的所有集合里强势插入第一个元素。
那么完整的代码如下：

点击查看代码

(define (subsets s)
    (if (null? s)
        (list nil)
        (let ((rest (subsets (cdr s))))
            (append rest (map (lambda(x) (cons (car s) x)) rest )))))