Marvin's Blog【程式人生】

Ability will never catch up with the demand for it

01 Oct 2020

The Little Schemer读书笔记(五)

The Little Schemer第七章Friends and Relations阅读笔记。

第七章首先出场的是set?,用来判断一个lat(list of atoms)中是否有重复的atom。

 (define set?
    (lambda (lat)
      (cond
        ((null? lat) #t)
        (else (cond
                ((member? (car lat) (cdr lat)) #f)
                (else set? (cdr lat)))))))

可以进行简化一下:

 (define set?
    (lambda (lat)
      (cond
        ((null? lat) #t)
        ((member? (car lat) (cdr lat)) #f)
        (else set? (cdr lat)))))

随之出来的是makeset,也就是去除lat中重复的部分:

 (define makeset
    (lambda (lat)
      (cond
        ((null? lat) '())
        ((member? (car lat) (cdr lat)) (makeset (cdr lat)))
        (else (cons (car lat) (makeset (cdr lat)))))))

也可以用multirember来写makeset

 (define makeset
    (lambda (lat)
      (cond
        ((null? lat) '())
        (else (cons (car lat) (multirember (car lat) (cdr lat)))))))

书中对makeset的叙述:

The function makeset remembers to cons the first atom in the lat onto the result of the natural resurrection, after removing all occurrences of the first atom from the rest of the lat.

接下来,我们要定义subset?:

 (define subst?
    (lambda (set1 set2)
      (cond
        ((null? set1) #t)
        (else (cond
                ((member? (car set1) set2) (subset2 (cdr set1) set2))
                (else #f))))))

然后要定义的是eqset?,可以使用前面已经定义好的subset?:

 (define eqset?
    (lambda (set1 set2)
      (and (subset? set1 set2) (subset? set2 set1))))

个人觉得也可以不用subset?来定义eqset?:

 (define eqset?
    (lambda (set1 set2)
      (cond
        ((and (null? set1) (null? set2)) #t)
        ((or (null? set1) (null? set2) #f))
        (else (cond
                ((equal? (car set1) (car set2)) (eqset? (cdr set1) (cdr set2)))
                (else #f))))))

下一个是insersect?,用来判断两个set是否有交集:

 (define intersect?
    (lambda (set1 set2)
      (cond
        ((null? set1) #f)
        (else (cond
                ((member? (car set1) set2) #t)
                (else (intersect? (cdr set1) set2)))))))

简化版

(define intersect?
    (lambda (set1 set2)
      (cond
        ((null? set1) #f)
        ((member? (car set1) set2) #t)
        (else (intersect? (cdr set1) set2)))))

cond的第二个条件和第三个条件可以使用or联结起来:

 (define intersect?
    (lambda (set1 set2)
      (cond
        ((null? set1) #f)
        (else (or (member? (car set1) set2) (intersect? (cdr set1) set2))))))

如果说intersect?判断两个set是否有交集,那么intersect给出这个交集:

 (define intersect
    (lambda (set1 set2)
      (cond
        ((null? set1) '())
        (else (cond
                ((member? (car set1) set2)
                 (cons (car set1) (insersect (cdr set1) set2)))
                (else (intersect (cdr set1) set2)))))))

接下来要出场的是union,给出两个set的并集。

 (define union
    (lambda (set1 set2)
      (cond
        ((null? set1) '())
        (else (cond
                ((member? (car set1) set2) (union (cdr set1) set2))
                (else (cons (car set1) (union (cdr set1) set2))))))))

接下来是一个根据代码猜功能的测试,下面是代码:

(define xxx
    (lambda (set1 set2)
      (cond
        ((null? set1) '())
        ((member? (car set1) set2) (xxx (cdr set1) set2))
        (else (cons (car set1) (xxx (cdr set1) set2))))))

书中关于上面这段代码的描述:

It is a function that returns all the atoms in set1 that are not in set2. That is, xxx is the (set) difference function.

下一位是intersectall,其参数是一个list of list,结果是子list中共有的atom集合:(inersectall '((a b c) (c a d e) (e f g h a b)))的结果是(a)

(define intersectall
    (lambda (l-set)
      (cond
        ((null? (cdr l-set)) (car l-set))
        (else (intersect (car l-set) (insersectall (cdr l-set)))))))

intersectall要求list中必须有一个节点。然后通过对list两两进行intersect操作,从而得出最后的结果。

接下来引入一个概念,叫pair。所谓pair,就是包含两个节点的list。下面定义一个函数a-pair?,用来判断一个list是否是一个pair:

 (define a-pair?
    (lambda (x)
      (cond
        ((atom? x) #f)
        ((null? x) #f)
        ((null? (cdr x)) #f)
        ((null? (cdr (cdr x))) #t)
        (else #f))))

然后定义有几个辅助函数first, second, build来帮助处理pair。

 (define first
    (lambda (p)
      (cond
        (else (car p)))))
(define second
    (lambda (p)
      (cond
        (else (car (cdr p))))))
(define build
    (lambda (s1 s2)
      (cond
        (else (cons s1 (cons s2 '()))))))

接着导出rel的概念。一个rel是一众pair的集合。fun?函数操作在一个rel之上,判断rel中的pair的第一个节点是否有重复的:

(define fun?
    (lambda (rel)
      (set? (firsts rel))))

对于rel的下一个操作是revrel,用于置换rel中每个pair中的元素。

(define revrel
    (lambda (rel)
      (cond
        ((null? rel) '())
        (else (cons (build
                      (second (car rel))
                      (first (car rel)))
                (revrel (cdr rel)))))))

可以提取一个专用的函数来置换pair中的节点:

 (define revpair
    (lambda (pair)
      (build (second pair) (first pair))))

这样revrel可以简化成:

(define revrel
    (lambda (rel)
      (cond
        ((null? rel) '())
        (else (cons (revpair (car rel)) (revrel (cdr rel)))))))

下面的fullfun?用来判断rel中的pair的第二个节点是否有重复,如果有则返回#t:

 (define fullfun?
    (lambda (fun)
      (set? (seconds fun))))

书中给fullfun?的另一个名字叫做one-to-one?,可以这样定义:

 (define one-to-one?
    (lambda (fun)
      (fun? (revrel fun))))

本章的最后一页定义了cookies,估计是为了来调节气氛的:

(define cookies
    (lambda ()
      (bake
        ('(350 degrees))
        ('(12 minutes))
        (mix
          '(walnuts 1 cup)
          '(chocolate-chips 16 ounces)
          (mix
            (mix
              '(flour 2 cups)
              '(oatmeal 2 cups)
              '(salt .5 teaspoon)
              '(baking-powder 1 teaspoon)
              '(baking-soda 1 teaspoon))
            (mix
              '(eggs 2 large)
              '(vanilla 1 teaspoon)
              (cream
                '(butter 1 cup)
                '(sugar 2 cups))))))))

(本篇完)

comments powered by Disqus