【Scheme归纳】3 比较do, let, loop

阅读量：5809 次

发布时间：2019-06-18

本文共 7133 字，大约阅读时间需要 23 分钟。

对象的比较

eq?

这个函数用来比较2个对象的地址，如果相同的话就返回#t。在Scheme中真用#t表示，假则用#f。

例如，（eq? str str)返回#t，因为str本身的地址的是一样的，但是”scheme”和”scheme”则被存储在不同的地址中，因此函数返回#f。注意，不要用eq?来比较数字，因为在R5RS和MIT-Scheme中均没有被指定返回值，建议使用eqv?或者=代替。以下是一些示例：

(define str "scheme");Value: str(eq? str str);Value: #t(eq? "scheme" "scheme");Value:()

eqv?

该函数比较2个储存在内存中的对象的类型和值，如果类型和值都一致则返回#t。对于过程（lambda表达式）的比较依赖于具体的实现。这个函数不能用于类似于表和字符串一类的序列比较，因为尽管这些序列看起来是一致的，但它们存储在不同的地址中。以下同样是一些示例：

(eqv? 1.0 1.0);Value: #t(eqv? 1 1.0);Value: ()(eqv? (list 1 2 3) (list 1 23))               不要去比较序列;Value: ()(eqv? "scheme" "scheme");Value: ()

equal?

比较序列就应该这个函数了。

(equal? (list 1 2 3) (list 1 2 3));Value: #t(equal? "hello" "hello");Value #t

其它用于比较的函数

pair?如果对象为序对则返回#t；

list?如果对象是一个表则返回#t。要小心的是空表’()是一个表但是不是一个序对。

null?如果对象是空表’()的话就返回#t。

symbol?如果对象是一个符号则返回#t。

char?如果对象是一个字符则返回#t。

string?如果对象是一个字符串则返回#t。

number?如果对象是一个数字则返回#t。

complex?如果对象是一个复数则返回#t。

real?如果对象是一个实数则返回#t。

rational?如果对象是一个有理数则返回#t。

integer?如果对象是一个整数则返回#t。

exact?如果对象不是一个浮点数的话则返回#t。

inexact?如果对象是一个浮点数的话则返回#t。

odd?如果对象是一个奇数的话则返回#t。

even?如果对象是一个偶数的话则返回#t。

postitive?如果对象是一个正数的话则返回#t。

negative？如果对象是一个负数的话则返回#t。

zero?如果对象是零的话则返回#t。

类似于用<=等比较数字，在比较字符的时候可以使用char=?、char

递归与尾递归

在自己的定义中调用自己的函数叫做递归函数（Recursive Function）。想必大家都知道这些。

计算阶乘则是演示递归的典型示例。

(define (fact n)  (if (= n 1)       1       (* n(fact (- n 1)))))

因此(fact 5)的计算过程用以下方式可以说明得很明显。

(fact 5)=> 5 * (fact 4)=> 5 * 4 * (fact 3)=> 5 * 4 * 3 * (fact 2)=> 5 * 4 * 3 * 2 * (fact 1)=> 5 * 4 * 3 * 2 * 1=> 5 * 4 * 3 * 2=> 5 * 4 * 6=> 5 * 24=> 120

但由于(fact 5),(fact 4)…(fact 1)都被分配了不同的存储空间，直到(fact(- i 1))返回一个值前，(fact i)都会被保存在内存中，由于存在函数调用的开销，这也就意味着会占用更多的内存空间和计算时间。

这种时候，使用尾递归则包含了计算结果，当计算结束时直接将其返回。尤其是Scheme规范要求尾递归调用转化为循环，因此尾递归调用就不存在函数调用开销。以下就是fact函数的尾递归版本。

(define (fact-tail n)  (fact-rec n n))(define (fact-rec n p)  (if (= n 1)      p      (let ((m (- n 1)))(fact-rec m (* p m)))))

同时，计算过程如下。

(fact-tail 5)⇒(fact-rec 5 5)⇒(fact-rec 4 20)⇒(fact-rec 3 60)⇒(fact-rec 2 120)⇒(fact-rec 1 120)⇒120

就是因为使用fact-rec并不用等待其它函数的计算结果，因此当它计算结束时即从内存中释放。fact-rec的参数不断在变化，这实际上就相当于是一种循环。就如同上文说到的，Scheme将尾递归转化为循环。

我们先来看看2个递归的例子。

(define (my-length ls)  (if (null? ls)      0      (+ 1 (my-length(cdr ls)))))(define (remove x ls)  (if (null? ls)     '()      (let ((h (car ls)))        ((if (eqv? x h) (lambda (y) y) (lambda (y) (cons h y)))         (remove x (cdr ls))))))

这2个例子的一个很明显的区别在于它们各自最后让递归过程停止的对象不同，前者是0，后者是’()。对于前者，我们要算出的是ls中元素的个数，后者则是将ls中的x元素去掉。前者最后返回的是数，后者则是表。

下面我们通过具体的示例来深入了解这两者之间的关系。

求和由数构成的表中的元素

递归版：

(define (my-sum ls)  (if (null? ls)     0      (+ (car ls) (my-sum (cdr ls)))))

尾递归版：

(define (my-sum-tail ls)  (my-sum-rec ls 0))(define (my-sum-rec ls n)  (if (null? ls)      n      (my-sum-rec (cdr ls) (+ n (car ls)))))

前者最后当ls为空是，返回0给+这个操作；后者的+操作则在my-sum-rec这个函数的参数位置，因此最后返回的是整个运算的结果n。前者通过不断地加上(car ls)来达到最终的目的；后者则通过不断的循环，将+操作的最终结果赋值给n。

named let

named let也可以用来表示循环，以下这个fact-let函数使用了一个loop，这和上文中的fact-rec函数是有很大区别的。在代码的第二行，代码将参数n1和p都初始化为n。当每次循环后，参数都在最后一行进行更新，此处的更新为：将n1减1，而将p乘以(n1-1)。

(define (fact-let n)  (let loop ((n1 n)(p n))               (if(= n1 1)                          p        (let ((m (- n1 1)))          (loop m (* p m))))))

当然了，如果觉得有了一个let在这里比较难以理解，下面这样也是可以的，不过上面这张方式更加简洁明了罢了。

(define (fact-let n)  (let loop ((n1 n) (p n))    (if (= n1 1)        p        (loop (- n1 1) (* p (- n1 1)))))

同样，我们通过对比递归来理解named let。

我们要做的是通过函数求出x元素在ls中的位置，索引从0开始，如果不在ls中则返回#f。

递归版：

(define (position x ls)  (position-aux x ls 0))(define (position-aux x ls i)  (cond   ((null? ls) #f)   ((eqv? x (car ls)) i)   (else (position-aux x (cdr ls) (1+ i)))))

named let版：

(define (position x ls)  (let loop((ls0 ls) (i 0))    (cond     ((null? ls0)#f)     ((eqv? x (car ls0)) i)     (else (loop (cdr ls0)(1+ i))))))

后者就像嵌套一般，进入了递归版的第二行代码。前者的else后面，通过函数调用返回自身；后者则很直接地通过更新参数来达到和递归同样的目的。后者我们先将ls赋值给ls0，通过不断的(cdrls0)来更新，先将0赋值给i，通过不断的(1+ i)来更新，这和递归中最后一行有着异曲同工之妙。

下面我们再通过尾递归来理解named let，多角度的对比，能够使我们更清晰的理解和加深印象。

这些的示例都很简单，基本上各大书籍文档中都大同小异，下面我们通过一个函数来反转ls中的所有元素。

尾递归版：

(define (my-reverse ls)  (my-reverse-rec ls ()))(define (my-reverse-rec ls0 ls1)  (if (null? ls0)      ls1      (my-reverse-rec (cdr ls0) (cons (car ls0) ls1))))

named let版：

(define (my-reverse-letls)  (let loop ((ls0 ls) (ls1 ()))    (if (null? ls0)        ls1        (loop (cdr ls0)(cons (car ls0) ls1)))))

我们很容易的看到两个版本的最后一行几乎一模一样；后者的第二行也相当于将前者的第二行代码并到第三行代码一样。由此可见，named let也不过是个皮囊而已，正在的动力依旧来源于不断的更新。

如果对named let感兴趣的话，可以看看这道题：。

letrec

letrec类似于let，不过它允许让一个名字递归地调用它自身。通常letrec都用于定义复杂的递归函数。

依旧是这个经典的示例：

(define (fact-letrec n)  (letrec ((iter (lambda (n1 p) (if (= n1 1) p (let ((m (- n1 1))) (iterm (* p m)))))))        (iter n n)))

倒数第二行的代码中，局部变量iter可以在它的定义里面引用它自己。而语法letrec是定义局部变量约定俗成的方式。

还是老规矩，对比出真知，我们先来看看上面第二大节中用来对比过的求和的例子。

我还在再次将它们贴出来好了。

尾递归版：

(define (my-sum-tail ls)  (my-sum-rec ls0))(define (my-sum-rec ls n)  (if (null? ls)      n      (my-sum-rec (cdr ls) (+ n (car ls)))))

letrec版:

(define (my-sum-letrec ls)  (letrec((iter(lambda(ls0 n) (if(null? ls0) n (iter (cdr ls0) (+ (car ls0) n))))))    (iter ls0)))

我们可以看出后者的最后一行的ls和0被赋值到第二行的ls0和n中，然后再倒数第二行中得到更新。下面我们再来看一个示例，这是将一个代表正整数的字符串转化为对应整数。例如“ 3389”会被转化为3389。不过只是个示例而已，不需要去检查那些不合法的输入。符到整数的转化是通过将字符#\0……#\9的ASCII减去48，可以使用函数char->integer来获得字符的ASCII码。函数string->list可以将字符串转化为由字符构成的表。

尾递归版本：

(define (my-string->integer str)  (char2int (string->list str) 0))(define (char2int ls n)  (if (null? ls)      n      (char2int (cdr ls)               (+ (- (char->integer (car ls)) 48)                  (* n 10))))

named let版本：

(define (my-string->integer-letstr)  (let loop ((ls0 (string->list str)) (n0))    (if (null? ls0)        n        (loop (cdr ls0)             (+ (- (char->integer (car ls0)) 48) (* n 10))))))

letrec版本：

(define (my-string->integer-letrec str)  (letrec ((iter (lambda (ls0 n) (if (null? ls0) n (iter (cdr ls0) (+ (- (char->integer (car ls0)) 48) (* n 10)))))))    (iter (string->list str) 0)))

将尾递归中的第二行并到第三行就相当于named let版本的第二行了，更新的过程也大同小异。letrec版本的也和这个类似，将最后一行并到第二行也是一样的，第五行到第七行均为参数的更新，更新的过程也就是求解的过程。

do

就像在C系列语言中我们通常用while比较多而do比较少一样，在scheme中do也并不常见，但语法do也可以用于表达重复。它的格式如下：

(do binds   (predicate value)    body)

变量在binds部分被绑定，而如果predicate被求值为真，则函数从循环中逃逸（escape）出来，并返回值value，否则循环继续进行。binds部分的格式如下所示：

[binds] - ((p1 i1 u1) (p2 i2u2)...)

变量p1,p2,…被分别初始化为i1,i2,…并在循环后分别被更新为u1,u2,…。

最后一次fact函数的do表达式版本。

(define (fact-do n)  (do ((n1 n (- n1 1)) (p n (* p (- n1 1))))     ((= n1 1) p)))

变量n1和p分别被初始化为n和n，在每次循环后分别被减去1和乘以(n1-1)。当n1变为1时，函数返回p。此处的n1和p分别相当于上文中的p1和p2，n1后面的n和p后面的n分别相当于上文中的i1和i2，(- n1 1)和(* p (-n1 1))分别相当于上文中的u1和u2。

do也挺难的，不过我觉得letrec更加难以灵活运用。

下面我们换一种方式，通过各个示例的do版本之间的联系来对比加深对这些语法的理解。

(define (my-reverse-do ls)  (do ((ls0 ls (cdr ls0)) (ls1() (cons (car ls0) ls1)))      ((null? ls0) ls1)))(define (my-sum-do ls)  (do ((ls0 ls (cdr ls0))(n0 (+ n (car ls0))))      ((null? ls0) n)))(define (my-string->integer-do str)  (do ((ls0 (string->list str)(cdr ls0))       (n0 (+ (- (char->integer (car ls0)) 48) (* n1 0))))      ((null? ls0) n)))

加色部分通过上文的讲解相信很容易理解了，最后一行都是do的终止的判断，为真的时候则求值并返回最后一个ls1(或n)。