乐正

Actions speak louder than words.

Eopl-ex2-1

Exercise 2.1 [*]

Implement the four required operations for bigits. Then use your implementation to calculate the factorial of 10. How does the execution time vary as this argument changes? How does the execution time vary as the base changes? Explain why.

Answer

以10为底的 bigint (ex2-1.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
; 实现以 10 为底的 bigint
(define zero
  (lambda () '()))

(define is-zero?
  (lambda (n) (null? n)))

(define is-one?
  (lambda (n) (equal? (simplify n) '(1))))

(define successor
  (lambda (n)
    (if (is-zero? n)
        (cons 1 '())
        (if (= (+ (car n) 1) 10)
            (simplify (cons 0 (successor (cdr n))))
            (simplify (cons (+ (car n) 1) (cdr n)))))))

(define predecessor
  (lambda (n)
    (if (is-zero? n)
        '()
        (if (= (car n) 0)
            (simplify (cons 9 (predecessor (cdr n))))
            (simplify (cons (- (car n) 1) (cdr n)))))))

(define plus
  (lambda (x y)
    (if (is-zero? x)
        y
        (successor (plus (predecessor x) y)))))

; 化简 bigint,除去不必要的 0
; 比如将 '(0) 化简成 '()
(define simplify
  (lambda (n)
    (if (null? n)
        '()
        (if (and (= (car n) 0)
                 (null? (simplify (cdr n))))
            '()
            (cons (car n) (simplify (cdr n)))))))

; 乘法可以使用如下的递归方式描述
; n x m ::= m + (n - 1) x m
(define multiply
  (lambda (x y)
    (if (or (is-zero? x)
            (is-zero? y))
        (zero)
        (plus (multiply (predecessor x) y) y))))

(define factorial
  (lambda (n)
    (if (is-one? n)
        n
        (multiply n (factorial (predecessor n))))))

Example

1
2
3
(define foo '(0 1))
(factorial foo)
; => (0 0 8 8 2 6 3)

draft

« Data Abstraction 笔记

Comments