LISP Programming 1062_ex9

http://erdos.csie.ncnu.edu.tw/~klim/scheme/lisp-1062.html

exercise 9: enumerating tuples
•Define a procedure, (enum-tuples list-1 list-2 .... list-k) which will
generate a list of k-tuples. The tuples contains all combinations of
elements from each list.

$ scheme48
> ,load ex9-enum-tuples.scm
> 
> (enum-tuples)
()
> (enum-tuples '(x y z))
((x) (y) (z))
> (enum-tuples '(a b c) '(hello world))
((a hello) (b hello) (c hello) (a world) (b world) (c world))
> (enum-tuples '(1 2) '(h i j k))
((1 h) (2 h) (1 i) (2 i) (1 j) (2 j) (1 k) (2 k))
> (enum-tuples '(hello ohio) '(101 39 11) '(good fine))  
((hello 101 good) (ohio 101 good) (hello 39 good) (ohio 39 good)
(hello 11 good) (ohio 11 good) (hello 101 fine) (ohio 101 fine)
(hello 39 fine) (ohio 39 fine) (hello 11 fine) (ohio 11 fine))
> ,exit
$

解答:

;exer9 enumerating tuples
(define proc-list
    (lambda (lst f)
        (cond
            ((null? lst) '())
            (else
            (append (f (car lst)) (proc-list (cdr lst) f)))))
) ;proc-list END
(define combine
  (lambda (list1 list2)
    (proc-list list1 (lambda (x)
                     (map (lambda (y) (list x y)) list2))))
) ;combine END
(define enum-tuples
  (lambda (x-lst . y-lst*)
    (cond
      ((null? y-lst*) (map list x-lst)) ;case1: (enum-tuples '(x y z))
      ((null? (cdr y-lst*)) (combine x-lst (car y-lst*)))
      (else
          (proc-list x-lst (lambda (x)
                           (map (lambda (y) (cons x y))
                                (apply enum-tuples y-lst*)))))))
) ;enum-tuples END

執行結果：

LISP Programming 1062_ex8

http://erdos.csie.ncnu.edu.tw/~klim/scheme/lisp-1062.html

exercise 8: enumerate a tree with sequence interface
•Rewrite (enum-tree T) with accumulate and map.

解答:

;enumerate tree
(define (enumerate-tree tree)
  (cond ((null? tree) '())
        ((not (pair? tree))
              (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))
;use map list a tree to see ex2.30
;(1) map a tree
(define (lst x) (append x))
(define (map-tree t)
    (enumerate-tree
        (map (lambda (sub-tree)
             (if (pair? sub-tree)
                 (map-tree sub-tree)
                 (lst sub-tree)))
                t)))
(define nil '())

;p78 accumulate.scm
(define (accumulate op initial sequence)
    (if (null? sequence)
        initial
        (op (car sequence)
            (accumulate op initial (cdr sequence))))
)
;(2) accumulate a tree
(define (enum-tree t )
   (accumulate cons
               (list)         ;empty list
               (map-tree t)))

執行結果：

LISP Programming 1062_ex7

http://erdos.csie.ncnu.edu.tw/~klim/scheme/lisp-1062.html

exercise 7: mapping over trees
•Refer to exercise 2.31.

解答:

(define l (list 1 (list 2 3 (list 4 5))))

(define (sq x) (* x x))

(define (tree-map f tree)
  (cond ((null? tree)
          '())
        ((not (pair? tree))
          (f tree))
        (else
          (cons (tree-map f (car tree))
                (tree-map f (cdr tree))))))

執行結果：

LISP Programming 1062_ex6

http://erdos.csie.ncnu.edu.tw/~klim/scheme/lisp-1062.html

exercise 6: representing a pair with a number
•Refer to exercise 2.5.
•Note the requirement of nonnegative is removed. Your method 
should accept two integers.

解答:

(define (num-cons a b)
    (* (expt 2 a) (expt 3 b)))

(define (num-car n)
  (if (= 0 (modulo n 2))
      (+ 1 (num-car (/ n 2)))
      0))

(define (num-cdr n)
  (if (= 0 (modulo n 3))
      (+ 1 (num-cdr (/ n 3)))
      0))

執行結果： 

LISP Programming 1062_ex5

http://erdos.csie.ncnu.edu.tw/~klim/scheme/lisp-1062.html

exercise 5: calculating continued-fraction
•Refer to exercise 1.37.(參考這篇：黃金分割)
•You have to write two procedures. One is (cont-frac n d k) and another is (pi epsilon).
•The "cont-frac" should be implemented in linear iterative way.
•To calculate pi, the sequence N_i is: 4, 1^2, 2^2, 3^2, ...
 and the sequence D_i is: 1, 3, 5, 7, ...
•To approximate pi, calculate (cont-frac n d 1), (cont-fract n d 2), .. until two consecutive values
 are  close enough, that is, the distance between them is less than epsilon.

$ scheme48
> ,load ex5.scm
> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 100)
0.6180339887498948
> (pi 0.001)
3.141463414634146
> (pi 0.0001)
3.1415888250921244
> (pi 0.0000000000001)
3.141592653589791
> ,exit
$
解答說明請參考：【Scheme】連分法求pi

解答:

;continued fraction calc pi
(define (cont-frac n d k)
   (define (frac-iter i result)
       (if (= i 0)
           result
           (frac-iter (- i 1.0) (/ (n i) (+ (d i) result)))))
   (frac-iter (- k 1.0) (/ (n k) (d k))))
(define (calc-pi k)
    (define (d i)
        (- (* 2 i) 1))
    (define (n i)
        (if (= i 1)
            4
            (* (- i 1) (- i 1))))
    (cont-frac n d k))
(define (calc-enough index accuracy)
    (define next_i index) ;next_i=index
    (if (< (abs (- (calc-pi index) (calc-pi (+ next_i 1)))) accuracy)
        (calc-pi (+ next_i 1))               ;true
        (calc-enough (+ index 1) accuracy))) ;false
(define (pi accuracy)
    (calc-enough 1 accuracy))

執行結果：

【Scheme】連分法求Pi

題目要求:
•Refer to exercise 1.37.
•You have to write two procedures. One is (cont-frac n d k) and another is (pi epsilon).
•The "cont-frac" should be implemented in linear iterative way.
•To calculate pi, the sequence N_i is: 4, 1^2, 2^2, 3^2, ...
 and the sequence D_i is: 1, 3, 5, 7, ...
•To approximate pi, calculate (cont-frac n d 1), (cont-fract n d 2), .. until two consecutive values
 are  close enough, that is, the distance between them is less than epsilon.

參考SICP ex 1.37，寫兩個程序
1.  (cont-frac n d k) and (pi epsilon)
2. "cont-frac" 使用迭代法
3. 計算 Pi，序列N_i 是4，1^2，2^2，3^2 . . .D_i是 1，3，5，7 . . .
4. 近似求Pi，直到(cont-frac n d 1), (cont-fract n d 2)值小於精確值

首先 π 的連分公式如下:

其中4,1,4,9,16就是N_i 項; 而 1,3,5,7,9就是Ｄ_i項,
參考上一篇的(cont-frac)，迭代法程式:

(define (cont-frac-iter n d k)
   (define (frac-iter i result)
       (if (= i 0)
           result
           (frac-iter (- i 1) (/ (n i) (+ (d i) result)))))
   (frac-iter (- k 1) (/ (n k) (d k))))

接著解釋 n項 與 d項:
這裡要注意的是 
d項就是迭代 i值的(2*i-1)，例如第一項是(2*1-1)=1，第二項是(2*2-1)=3 . . .依此類推
而n項就是 迭代 i值的平方(i^2)，但要注意第一項是4，第二項是((2-1)^2)，第三項是((3-1)^2) . . .

(define (calc-pi k)
    (define (d i)
        (- (* 2 i) 1)) ;((2*i)-1)
    (define (n i)
        (if (= i 1)
            4
            (* (- i 1) (- i 1))))
    (cont-frac n d k))

這樣就可以求Pi，例如(calc-pi 10)，求出聯分法10項的Pi值: 
(calc-pi 10)
3.14159254044654 
(calc-pi 20)
3.14159265358979
用這種方式求Pi因為收斂很快所以不會花費太多時間。

接著要給精確值求出Pi，就是用迭代法每一次求出的Pi值與下一個項次比較，直到小於精確值為止
如:
(calc-pi 5)-(calc 6) < accuracy ?
如果是則停止
如果不是則(calc-pi 6)-(calc-pi 7)

(define (inc x)
    (+ x 1))
(define (enough-pi index accuracy)
    (define next_i index) ;next_i=index
    (if (< (abs (- (calc-pi index) (calc-pi (inc next_i)))) accuracy)
        (calc-pi (inc next_i))            ;true
        (enough-pi (inc index) accuracy)) ;false
)
(define (pi accuracy)
    (enough-pi 1 accuracy))

輸入與結果:
(pi 0.001)
3.14146341463415
(pi 0.0001)
3.14158882509212
(pi 0.0000000000001)
3.14159265358979
如果將各項的輸出印出

index:5 next_i:5 err:0.001
3.14146341463415
在第5項的時候收斂到0.001

index:7 next_i:7 err:0.0001
3.14158882509212
在第7項的時候收斂到0.0001

index:19 next_i:19 err:1e-13
3.14159265358979
在第19項的時候收斂到0.0000000000001


參考:
1.維基百科圓周率
2. SICP Ex 1.37

【Scheme】SICP Ex.1.37

Exercise 1.37.  a. An infinite continued fraction is an expression of the form
在SICP練習1.37 中要求寫出連分法的表示，公式如下:

而這個除法式可以用一個遞迴表達式來表示如下：

其中函數 cf(i) 表示連分式的第 i 個項。

因此Scheme程式遞迴寫法如下:

(define (cont-frac n d k)
  (define (frac i)
     (if (< i k)
         (/ (n i) (+ (d i) (frac (+ i 1))))
         (/ (n i) (d i))))
  (frac 1))

迭代寫法如下:

(define (cont-frac-iter n d k)
   (define (frac-iter i result)
       (if (= i 0)
           result
           (frac-iter (- i 1) (/ (n i) (+ (d i) result)))))
   (frac-iter (- k 1) (/ (n k) (d k))))

可以用下面的近似驗證:

> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 100)0.618033988749895

這就是黃金分割比例值。


參考:
1. SCIP 教材

LISP Programming 1062_ex3

http://erdos.csie.ncnu.edu.tw/~klim/scheme/lisp-1062.html

exercise 3: linear recursive and linear iterative
Refer to exercise 1.11 but the formula is changed to
  f(n) = n if n < 3
  f(n) = 2*f(n-1) + f(n-2) + f(n-3) if n ≥ 3 and n is even
  f(n) = 2*f(n-1) - f(n-2) + f(n-3) if n ≥ 3 and n is odd
Note that you have to write two procedures. One is written
in recursive way and another in linear iterative way.

解答:

;f by means of a recursive process
(define (f-res n)
    (if (< n 3)
        n  ; n<3 , f(n)=n
        (if (odd? n)
            (+ (- (* 2 (f-res (- n 1))) 
               (f-res (- n 2))) 
            (f-res (- n 3))) ; n is odd
            
            (+ (+ (* 2 (f-res (- n 1))) 
               (f-res (- n 2))) 
            (f-res (- n 3)))))) ; n is even
(define (f n)
    (f-res n))

執行結果：


 

LISP Programming 1062_ex2

exercise 2: improving the good-enough?
Refer to exercise 1.7

解答:
;exercise 2: improving the good-enough?
(define (average x y)
    (/ (+ x y) 2))
(define (improve guess x)
    (average guess (/ x guess))
)
(define (good-enough? old-guess new-guess)
    ;(> 0.01 (/ (abs (- new-guess old-guess)) old-guess))
    (< (/ (abs (- new-guess old-guess)) old-guess) 0.01)
)
(define (sqrt-iter guess x)
    (if (good-enough? guess (improve guess x))  ;調用新的good-enough?
        (improve guess x)
        (sqrt-iter (improve guess x) x)
    )
)
(define (sqrt x)
    (sqrt-iter 1.0 x))

執行結果：

LISP Programming 1062_ex1

exercise 1: figure out the sum of squares of the minimum two arguments
Write a procedure named 'sum-of-square-min-two' which accepts three  
arguments and will figure out the sum of squares of the minimum two
arguments. 

$ scheme48
> ,load ex1-sum-square-min-two.scm
> 
> (sum-of-square-min-two 1 2 3)
5
> (sum-of-square-min-two 1 2 -3)
10
> (sum-of-square-min-two 2 2 2)
8
> ,exit
$

解答:
;figure out the sum of squares of the minimum two arguments 
(define (square x)
      (* x x))
(define (min-two-square a b c)
    (if (<= a b)
        (if (<= b c)
            (list (square a) (square b))
            (list (square a) (square c)))
        (if (<= a c )
            (list (square b) (square a))
            (list (square b) (square c)))))
(define (sum-data x y)
    (+ x y))
(define (sum-of-square-min-two a b c)
    (apply sum-data (min-two-square a b c)))

執行結果：

認識Scheme

   兒子大二下學期程式設計選了一門"LISP程式設計"，這門課選用的語言是 Scheme，
是 LISP 的其中一個方言，應該對大多數人都蠻陌生的吧，因為它的確不是業界主流的程式
語言。老實說，我比較希望他能選一些Python或是Java的課程，畢竟將來是要靠這些"吃飯"的。

   剛剛有提到Scheme是LISP的方言，是1975年誕生於MIT人工智慧實驗室的一門程式語言。
那Scheme是一個怎麼樣的程式語言呢?
簡單來說Scheme是一種函數語言程式，意思是說，盡量把所有的函數都想成/寫成數學上的函數。
如果說Python 裡所有東西都是物件;那Scheme裡所有東西都是函數。

   約耳談軟體在2005年曾發表過一篇《The Perils of JavaSchools（爪哇學校的危害）》，
就談到不少 Java 不適合作為「First Programming Language」的問題，如果 Java 不適合
初學者，那有什麼更好的語言適合教學嗎？Joel Spolsky 的建議是 Scheme，這個主要用於
人工智慧領域的古老程式語言，Scheme 當時是 MIT 等多所名校 Computer Science 系所
的必修課程。而他們所使用的教材就是這本「SICP」。
(註:MIT 之所以從 SICP 轉換到現在的Python課程編制(2008)，是因為他們重新規劃了學習
的主軸。)

  「SICP」是 Structure and Interpretation of Computer Programs 的簡稱，又稱為

魔法書。是當年 MIT 赫赫有名的 6.001，是 EECS 的入門課，而這本書也影響了後續許多 CS 
的教材，甚至影響了很多以寫程式為工作或是以此為興趣的人，MIT電腦科學課程用這本書
當教材足足用了30年。

   相較於C/C++，Python 等等這些主流的語言，教材的資源也相當多，而台灣坊間Scheme 的
資源卻是少之又少，教授上課所用的Scheme 教材是SICP線上英文版，我找來找去發現對岸
的相關簡體書還蠻多的，就買了一本來看看。

為什麼這本書對於「CS 入門」來說具有革命性的意義? 主要有下面兩點：
.只專注一件事：計算的本質
.使用 Scheme 當作主要的語言

   通常，Computer Science 相關的入門課程，可能會花上很多時間在熟悉某個「程式語言」
上面，而不是去了解程式本身；又或者是有了大量的類比，來介紹電腦是個怎麼樣的東西；
但是 SICP 只專注一件事，那就是計算的本質這件事。

程式語言專家、大評論家王垠說：
    編程不過是一門失傳的藝術的別名，這門藝術的名字叫做"思考"。 —— 王垠

   兒子在剛上大學的時候我再三叮嚀他一定要把 C語言學好，因為 C語言學好了再學其他語言就
會非常容易好上手，學習不同語言其實就是換個思考方式來實作;
但如果以為學好C 就一定能學好Scheme嗎? 看看書中的內容比我想像中還要難尤其是遞迴
(Recursion)，我們常說"換了屁股就換了腦袋"，面對Scheme真的要換個思考(腦袋)方式才
能寫出優雅的程式。

既然這樣就好好的修這門課，試著用不同的思考方式來解決問題吧。

L. Peter Deutsch程式設計師說過一段經典名句:

"To iterate is human, to recurse, divine."

有人翻成: 

"遞迴（recurse）只應天上有, 凡人該當用迴圈(iterate)"