这是一本用Scheme语言来介绍递归和函数式编程的书。与《计算机程序的构造和解释》当中使用的Racket语言几乎通用(Racket是Scheme的一种标准的分支，本书中涉及不到二者的区别，本文中两种语言不作区分）。据说用函数式语言（Scheme, Haskell等等）非常适合编写编译器，不过这本『The Little Schemer』还到不了编写编译器的难度，只需要识字和会数数就可以阅读（用Racket写编译器可以看《计算机程序的构造和解释》，笔记正在整理中）。使用Scheme递归地编写程序本质上是简单的模式识别，所以讲解递归和函数式编程，只使用基础的几个关键字：car, cdr, cons, eq?, null?, zero?, add1, sub1, number?, and, or, quote, lambda, define, cond。

Scheme语言是一种前缀表达，每个表达式使用一个括号括起来，括号中第一个项是运算符，后边的各项是参数，例如计算2和3相加，在Scheme中就使用(+ 2 3)。总是可以使用define关键字进行定义常量、函数等等。例如定义一个函数f对一个参数x起作用，得到结果是x+1，则可定义为(define (f x) (+ x 1))。

在本书中，首先引入一个atom?的定义，用于判断一个元素是否为“原子”：

（Scheme允许特殊符号用作表达式。对于结果为逻辑值的函数，一般用问号结尾表示，类似于其它语言中用is前缀（如isEmpty(),isZero()等））

(define atom?
  (lambda (x)
    (and (not (pair? x)) (not (null? x)))))

Chap.1

先了解基本Scheme的元素：原子、列表、集合。

原子：如下的各项都是原子，atom, turkey, 1492, u, *abc$。能够以任何字母、数字以及除了左右圆括号的其它符号，都可以作为原子。
列表：如下各项都是列表，(atom), (atom turkey or), ((atom turkey) or), (), (() () ())，只要是合法的括号对，每对括号中都是原子或列表，则它就是一个列表。
表达式：所有原子、所有列表，都是表达式.

car之法则：

基本元素car仅定义为针对非空列表

car是取列表的首个元素，cdr是取列表除car元素之外的部分。
列表l是(((hotdogs)) (and) (pickle) relish)，则(car l)是((hotdogs))，因为它是l的首个表达式，(cdr l)是((and) (pickle) relish)。
列表l是((a b c) x y z)，则(car l)是(a b c)，(cdr l)是(x y z)。
a是hotdog，要访问(car a)是错误的，因为不能对一个原子求car。
列表l是()，则(car l)是错误的，不能对一个空列表求car。

cdr之法则：

基本元素cdr仅定义为针对非空列表。任意非空列表的cdr总是另一个列表

car和cdr都要以非空列表作为参数。

定义a是原子peanut,l是列表(butter and jelly)，其cons运算(cons a l)是(peanut butter and jelly).表达式cons添加一个原子到一个列表的开头。cons有两个作为参数，第一个参数是表达式，第二个参数是任意列表，其结果是将这个表达式置于列表的最前。

cons之法则：

基本元件cons两个参数，第二个参数必须是一个列表，结果是一个列表。

引入基本元件null?，用于判断一个列表是否为空。

一个空列表可表达为(quote ())。
表达式(null? (quote ()))为真。
(null? (a b c))为假，因为(a b c)不是空列表。

null?之法则:

基本元件null?只针对列表

定义a1是原子Harry,定义a2是原子Harry，表达式(eq? a1 a2)的结果为真，二者是相同的原子

定义列表l是(Mary had a little lamb chop)，a是Mary,则(eq? (car l) a)是真。因为(car l)就是Mary,与a是相同的原子。

eq?之法则:

基本元件eq?需要两个参数，每个参数必须是非数字的原子

（不过某些标准下也可以用数字作为eq?的参数）

Chap.2 开始处理处理…反复处理

定义l是(Jack Sprat could eat no chicken fat)，由于l的每个元素都是原子，定义表达式lat?，用于判断l的所有元素是否全部为原子(lat? l)为真。
定义l是((Jack) Sprat could eat no chicken fat)，列表l中首个元素是列表不是原子，所以(lat? l)是假。

如何实现lat? 呢?就逐个元素用atom?运算判断一次，一旦有某个元素atom?运算为假，则lat?的值为假，否则直至最后列表为空的时候说明列表的所有元素都是原子则整个列表的内容全为原子，从而lat?值得到为真

(define lat?
  (lambda (l)
    (cond
      ((null? l) #t)
      ((atom? (car l)) (lat? (cdr l)))
      (else #f))))

基本元件cond是条件condition的功能，cond有不定数量个参数，每一个是一个列表组成，其中每个列表的第一个表达式是条件，当此条件满足时则执行第二个表达式，按照顺序进行匹配，一旦某个模式被匹配之后就执行，后续的匹配则不再执行。cond中使用else关键字，else作为条件的值永远为真，可以当作所有模式都不匹配的最后条件（类似C语言中switch的default关键字)。这就是函数式的模式匹配。

对于一个列表l，如果它是空列表，那么lat?是真，如果不是空列表，则判断列表首元素是否为atom?，如果首元素是个atom，则执行(lat? (cdr l))，也就是递归到列表的cdr继续这样执行，如果当前首元素不是atom，则cond的匹配将到else，而else的值为真，所以结果为假。

定义a是meat，列表l是(mashed potatoes and meat gravy)，则表达式(member? a l)表述原子a是列表l中的成员，得到的值为真，

Scheme十诫之第一诫：表达任意函数时，总将询问null?作为问题之首

由于需要判断原子a和l的某个元素判断，但判断之前必须保证l不是空表，永远不可能在空列表中找到原子a,所以如果列表为空表，则得到结果为假，否则，就可以对原子a和列表首元素(car l)进行判等eq?，若原子a与(car l)不相等，则继续递归地判断(member? a (cdr l))

(define member?
  (lambda (a l)
    (cond
      ((null? l) #f)
      (else (or (eq? (car l) a) (member? a (cdr l)))))))

Chap.3 用cons构筑恢宏

定义a是原子mint，lat是列表定义为(lamb chops and mint jelly)，表达式(rember a lat)的功能是将lat中首个出现的a删除，结果为删除首个出现a的新的列表。

与前边类似的，对于lat进行递归，如果lat是空列表，则返回空列表，否则对lat进行判断，比较lat的首项与a是否为同一原子，若是，则得到这个表达式之后的列表中的其它表达式，否则从列表下一个元素继续递归下去。

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      (else (cond
              ((eq? (car lat) a) (cdr lat))
              (else (rember a (cdr lat))))))))

对于a是bacon,列表lat是(bacon lettuce tomato)来说，这段rember能够实现地很好，但换一个测试数据，原子a是and，列表为(bacon lettuce tomato)，用这样定义的(rember a lat)运算，得到的结果是(tomato)而不是预想的(bacon lettuce tomato)。

Scheme十诫之第二诫：用cons构建列表

不难发现，上边的实现在(car lat)和a相等的时候，没有把a之前的那些记录下来，直接将前边的丢弃了再进行的递归。需要修改最后递归的逻辑：如果(car lat)和a不相等，那么得到的值是(car lat)和后边的(rember a (cdr lat))，用cons将(car lat)连在暂时不知道值的(rember a (cdr lat))最前。即：

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      (else (cond
              ((eq? (car lat) a) (cdr lat))
              (else (cons (car lat) (rember a (cdr lat)))))))))

这样执行(rember a lat)就得到正确的结果，并且如果a不在lat中，那么返回值也将是lat本身。rember逐一查找lat中的各个元素是否与原子a相等，如果(car lat)不是原子a，就保存car以便后续cons到结果上，如果rember找到了原子a，就剔除原子a并返回(cdr lat)，并将之前的原子接在返回值之前，也就得到了结果。

分析完还可以对其实现进行一点简化：

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) a) (cdr lat))
      (else (cons (car lat) (rember a (cdr lat)))))))

定义列表l是((apple peach pumpkin) (plum pear cherry) (bean carrot egglant))，表达式(firsts l)的值为(apple plum bean)。firsts函数以一个列表l为参数，这个列表中都是非空列表，这个函数将得到一个新列表，每个元素由列表l的每个内部列表的第一个表达式组成。
定义列表l是(((five plums) four) (eleven green oranges) ((no) more))，表达式(firsts l)的值为((five plums) eleven (no))。

先编写firsts的框架，与前述函数实现相近

(define firsts
  (lambda (l)
    (cond
      ((null? l) ...)
      (else (cons ... (firsts (cdr l)))))))

当列表l为空表的时候，往往是递归的结束，由于需要用cons将列表连接起来，所以不能返回逻辑值，不难看出这里应该返回一个空表(quote ())，当l不是空表的时候，要针对“典型元素”用cons建行构建

Scheme十诫之第三诫：构建列表时，描述第一个典型元素，之后cons该元素到一般性递归上

在firsts的典型元素的描述上，应当是(car l)的car，即(car (car l))，其后的(firsts (cdr l))即自然递归。这样就将firsts的实现补充完成：

(define firsts
  (lambda (l)
    (cond
      ((null? l) (quote ()))
      (else (cons (car (car l)) (firsts (cdr l)))))))

接下来，定义两个函数(insertR new old lat)和(insertL new old lat)，表示要在列表lat中找到首个出来的原子old，表达式insertR则在old之后插入这个原子，insertL在old之前插入这个原子。

(define insertR
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) old ) (cons old (cons new (cdr lat))))
      (else (cons (car lat) (insertR new old (cdr lat)))))))
(define insertL
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) old ) (cons new lat))
      (else (cons (car lat) (insertL new old (cdr lat)))))))

再复杂一点，定义一个函数(multirember a lat)，用于将列表lat中的所有原子a都删除。例如a是原子cup，列表lat是(coffee cup tea cup and hick cup)，则(multirember a lat)为(coffee tea and hick).

与之前rember的差别在于，当(eq? (car lat) a)为真的时候，不能直接返回后续的列表，而是需要继续进行一般性递归(multirember (cdr lat))，即：

(define multirember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) a) (multirember a (cdr lat)))
      (else (cons (car lat) (multirember a (cdr lat)))))))

Scheme十诫之第四诫：在递归时总是至少改变一个参数。该参数必须向着不断接近结束条件而改变。改变的参数必须在结束条件中得以测试

将insertR和insertL分别改写为multiinsertR与multiinsertL：

(define multiinsertR
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) old) (cons old (cons new (multiinsertR new old (cdr lat)))))
      (else (cons (car lat) (multiinsertR new old (cdr lat)))))))
(define multiinsertL
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) old) (cons new (cons old (multiinsertL new old (cdr lat)))))
      (else (cons (car lat) (multiinsertL new old (cdr lat)))))))