日拱一卒，伯克利教你学Lisp，CS61A作业9「建议收藏」

大家好，日拱一卒，我是梁唐。

我们继续来肝伯克利CS61A，这次我们看的是作业9，同样是基于Lisp语言的几个编程问题。本文始发于公众号：Coder梁

没接触过或者不了解Lisp的同学可以去翻一下我上一篇文章，里面有一些关于Lisp的简单介绍。

公开课视频

作业原文说明

Github

这一次的作业一共有五道题，题量和难度都不算大。

好了，废话不多说，我们来看题吧。

Q1: How Many Dots?

实现how-many-dots方法，它的输入是一个嵌套的scheme list s，返回的是s输出时包含的’点’的数量。

你可以假设s当中只包含数字。

提示：当一个pair中第二个元素不是一个标准的list时会出现’点’。

你可以使用pair?,null?,number?分别来判断一个值是否是一个pair, nil或数字

解答

这是一个简单的递归运用，对于一个嵌套的pair来说，它的first和second都有可能是一个pair。所以我们需要使用递归来解决。

如果s是一个pair，那么s当中点的数量等于s.first中点的数量和s.second中点的数量相加。还要加上s.first和s.second之间包含的点。什么情况下会在s.first和s.second之间出现点呢？答案很简单，当s.second是数字时。

(define (how-many-dots s)
  (cond 
        ((pair? s)
            (+  (how-many-dots (car s))
                (how-many-dots (cdr s))
                (if (number? (cdr s)) 1 0)
            )
        )
        (else 0)
  )
)

Differentiation（微分）

接下来需要我们开发一系列函数来实现代数当中的微分，要求能够求一个表达式中某一个变量的微分，变量可以是字母的形式。

derive过程接收一个代数表达式，和一个变量，返回这个表达式中该变量的微分。

微分是一个递归过程，包含了许多计算规则。

; derive returns the derivative of EXPR with respect to VAR
(define (derive expr var)
  (cond ((number? expr) 0)
        ((variable? expr) (if (same-variable? expr var) 1 0))
        ((sum? expr) (derive-sum expr var))
        ((product? expr) (derive-product expr var))
        ((exp? expr) (derive-exp expr var))
        (else 'Error)))

我们使用下列的数据抽象来实现，sums和products都是list，分别表示累加和累乘，更多的定义如下：

; Variables are represented as symbols
(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

; Numbers are compared with =
(define (=number? expr num)
  (and (number? expr) (= expr num)))

; Sums are represented as lists that start with +.
(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list '+ a1 a2))))
(define (sum? x)
  (and (list? x) (eq? (car x) '+)))
(define (addend s) (cadr s))
(define (augend s) (caddr s))

; Products are represented as lists that start with *.
(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list '* m1 m2))))
(define (product? x)
  (and (list? x) (eq? (car x) '*)))
(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))

为了简单起见，我们可以不用考虑使用链式法则嵌套求导的情况。

Q2: Derive Sum

实现derive-sum过程，对一个求和的过程求导。addend和augend表示加法当中相加的两个值。

解答

对于加法求导很简单，就是对相加的表达式进行分别求导，再相加

(define (derive-sum expr var)
    (make-sum (derive (addend expr) var) (derive (augend expr) var))
)

Q3: Derive Product

实现derive-product函数，对乘法表达式进行求导。它接收两个表达式相乘，返回它们的导数。

解答

对乘法求导稍微复杂一些，但是也不算太复杂，高数书里有现成的公式：

$(f(x)g(x))’ = f'(x)g(x) + f(x)g'(x)$

我们套用公式即可

(define (derive-product expr var)
    (make-sum 
      (make-product (derive (addend expr) var) (augend expr))
      (make-product (addend expr) (derive (augend expr) var))
    )
)

Q4: Make Exp

实现make-exp函数，base表示底数，exponent表示指数。base可以是任何表达式，但可以认为指数一定是非负整数。

对于指数是0或1，或者是底数也是整数的情况，你可以直接返回对应的结果。其他情况，你可以返回如下的表达式：(^ base exponent)

解答

由于exp表达式是(^ base exponent)的形式，所以base就是(cadr exp)，exponent就是(caddr exp)。

make-exp过程也简单，我们首先判断指数，如果指数为0，那么结果就是1，如果指数为1，结果就是base。否则则要判断底数是否是数字，如果是数字可以直接求出结果。否则生成对应的表达式。

(define (make-exp base exponent)
    (cond ((=number? exponent 0) 1)
          ((=number? exponent 1) base)
          ((and (number? base) (number? exponent)) (expt base exponent))
          (else (list '^ base exponent))
    )
)

(define (base exp)
    (cadr exp)
)

(define (exponent exp)
    (caddr exp)
)

(define (exp? exp)
    (and (list? exp) (eq? (car exp) '^))
)

Q5: Derive Exp

实现derive-exp函数，利用幂函数的规则进行求导。

解答

我们套用一下幂函数的求导公式：

$(f^a(x))’=af(x)^{a-1}*f'(x)$

我们可以使用make-product函数来求这三项的乘积：(exponent exp),(derive (base exp) var), (make-exp (base exp) (make-sum (exponent exp) (- 1)))

(define (derive-exp exp var)
    (make-product
      (make-product (exponent exp) (derive (base exp) var))
      (make-exp (base exp) (make-sum (exponent exp) (- 1)))
    )
)