2019年11月25日

Scheme Tutorial 2

local variables

用 let 定義 local variable,body由任意多個S-表達式構成,變數的Scopebody,只在body 中有效。

(let binds body)

;binds的格式
[binds] → ((p1 v1) (p2 v2) ...)

ex:

(let ((i 1) (j 2))
  (+ i j))
;Value: 3

let 可以嵌套使用

(let ((i 1))
  (let ((j (+ i 2)))
    (* i j)))
;Value: 3

因變數的作用域僅在body中,下列代碼會產生錯誤,因為在變量j的作用域中沒有變數i的定義。

(let ((i 1) (j (+ i 2)))
  (* i j))
;Error

let*表達式可以用於引用定義在同一個綁定中的變量。實際上,let*只是嵌套的let表達式的 syntax sugar 而已。

(let* ((i 1) (j (+ i 2)))
  (* i j))
;Value: 3

ex: 計算一元二次方程式的解。它需要三個參數代表係數:abcax^2 + bx + c = 0),計算結果傳回一個存放答案的實數表。

(define (quadric-equation a b c)
  (if (zero? a)
      'error                                      ; 1 如果二次項係數 a為0,函數返回'error
      (let ((d (- (* b b) (* 4 a c))))            ; 2 如果a ≠ 0,則將變數d與判別式(b^2 - 4ac)的值綁定
        (if (negative? d)
            '()                                      ; 3 如果d為負數,則返回'()
            (let ((e (/ b a -2)))                    ; 4 如果d不為負數,則將變數 e 與-b/2a 綁定
                (if (zero? d)
                    (list e)                            ; 5 如果 d為0,則返回一個包含e的表
                    (let ((f (/ (sqrt d) a 2)))         ; 6 如果 d是正數,則將變數 f 與√(d/2a)綁定,並返回由(+ e f)和(- e f)> 構成的表
                    (list (+ e f) (- e f)))))))))

(quadric-equation 3 5 2)  ; solution of 3x^2+5x+2=0
;Value 12: (-2/3 -1)

let expression 實際上只是 lambda expression 的 syntax sugar

(let ((p1 v1) (p2 v2) ...) exp1 exp2 ...)
;⇒
((lambda (p1 p2 ...)
    exp1 exp2 ...) v1 v2)

因為 lambda 用來定義函數,同時定義了該變數的作用範圍

ex: 用一個初始速度v和與水平面所成夾角a來計算飛行距離

(define (throw v a)
  (let ((r (/ (* 4 a (atan 1.0)) 180)))  ; (define pi (* 4 (atan 1.0)))  r 可將 degree 轉換為 radian
    (/ (* 2 v v (cos r) (sin r)) 9.8)))  ; 初始水平、竪直分速度分別表示為:v*cos(theta1)和v*sin(theta1)  落地時瞬時竪直分速度為-Vy  自由落體時間 2Vy = g*t


(throw 40 30)
;Value: 141.39190265868385

在 scheme 中,變數的作用範圍由 source code 決定,這稱為 lexical closure

Looping 迴圈

在 scheme 通常用遞迴來處理 looping

Recursion 遞迴

在函數定義中呼叫函數本身,就稱為遞迴函數。

ex: 計算階乘

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

過程如下

(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

list 可以用遞迴的方式定義,例如讓 list 裡面所有元素都乘以2 可這樣寫

(define (list*2 ls)
  (if (null? ls)
      '()
      (cons (* 2 (car ls))
           (list*2 (cdr ls)))))

(list*2 (list 1 2 3 4 5))
;Value 8: (2 4 6 8 10)

ex:

; 1 計算 list 內元素的個數
(define (my-length ls)
  (if (null? ls)
      0
      (+ 1 (my-length (cdr ls)))))

; 2 加總 list 內所有元素
(define (my-sum ls)
  (if (null? ls)
      0
      (+ (car ls) (my-sum (cdr ls)))))

; 3 從 ls 中刪除 x 後得到的表
(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))))))

; 4 傳回 x 在 ls 中首次出現的位置。索引從0開始。如果 x 不在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)))))

尾遞迴

普通的遞迴並不高效因為它既浪費儲存空間又具有呼叫函數的開銷。尾遞迴函數包含了計算結果,當計算結束時直接將其回傳。另外由於Scheme規範中要求尾遞迴呼叫轉化為循環,因此尾遞迴呼叫就不存在呼叫函數的開銷。

ex: 階乘的尾遞迴版本

(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

Scheme將尾遞迴轉化為循環,Scheme就無需提供循環的語法來實現 looping。

ex:

; 1 翻轉 list 元素的順序
(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))))

;-------------------
; 2 加總 list
(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)))))

;--------------------
; 3 將一個代表正整數的字串轉化為對應整數。 例如 "1232" 轉換為 1232,不檢查非法的字元
; 字元到整數的轉化是通過將字元 #\0 …… #\9 的ASCII減去48,可以使用函數char->integer來獲得字符的ASCII碼。
; 函數 string->list 可以將字串轉化為由字元構成的 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 有命名的 let

named let 可用來處理 looping

ex: 用 named let 實作階乘

(define (fact-let n)
  (let loop((n1 n) (p n))     ; 1  將參數 n1 與 p 都初始化為 n
    (if (= n1 1)
      p
      (let ((m (- n1 1)))
      (loop m (* p m))))))    ; 2  每一次循環時,n1 會減 1, p 會乘以 (n1-1)

ex:

; 1  從 ls 中刪除 x 後得到的表
(define (remove x ls)
  (let loop( (ls0 ls) (ls1 ()) )
    (if (null? ls0)
      (reverse ls1)
      (loop
        (cdr ls0)
        (if (eqv? x (car ls0))
            ls1
            (cons (car ls0) ls1) )))))

; 2  傳回 x 在 ls 中首次出現的位置。索引從0開始。如果 x 不在ls中,函數傳回 #f
(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))))))

; 3  翻轉 list 元素的順序
(define (my-reverse-let ls)
  (let loop( (ls0 ls) (ls1 ()) )
    (if (null? ls0)
      ls1
      (loop (cdr ls0) (cons (car ls0) ls1)))))

; 4  加總 list
(define (my-sum-let ls)
  (let loop((ls0 ls) (n 0))
    (if (null? ls0)
  n
  (loop (cdr ls0) (+ (car ls0) n)))))

; 5  將一個代表正整數的字串轉化為對應整數
(define (my-string->integer-let str)
  (let loop((ls0 (string->list str)) (n 0))
    (if (null? ls0)
  n
  (loop (cdr ls0)
        (+ (- (char->integer (car ls0)) 48)
     (* n 10))))))

; 6  range函數:傳回一個從0到n的表(但不包含n)
(define (range n)
  (let loop((i 0) (ls1 ()))
    (if (= i n)
      (reverse ls1)
      (loop (1+ i) (cons i ls1)))))

letrec

letrec 類似let,但允許一個名字遞迴呼叫自己。通常用來定義複雜的遞迴函數 recursive local functions。

; 階乘的 letrec 版本
(define (fact-letrec n)
  (letrec ((iter (lambda (n1 p)
       (if (= n1 1)
           p
           (let ((m (- n1 1)))  (iter m (* p m))) ))))     ; iter 可在定義中引用自己
       (iter n n) ))

letrec 的語法,前面是變數定義區塊,<body> 是執行區塊

(letrec ((<variable> <init>) ...) <body>) 

letrec最常見的用法就是用於綁定函數對象,讓變數定義區塊V裡面定義的所有變量可以在執行時相互引用,不受位置前後的限制

(letrec ((x (lambda () (+ y y)))
         (y 100))
    (+ (x) y))

; 執行(+ (x) y)時,雖然 y在x之後才綁定的,函數對象x可以讀取y對象的值

(define x (lambda () (+ y y)))

(define y 100)

(+ (x) y)

ex:

; 1  翻轉 list 元素的順序
(define (my-reverse-letrec ls)
  (letrec ((iter (lambda (ls0 ls1)
       (if (null? ls0)
           ls1
           (iter (cdr ls0) (cons (car ls0) ls1))))))
    (iter ls ())))

; 2  加總 list
(define (my-sum-letrec ls)
  (letrec ((iter (lambda (ls0 n)
       (if (null? ls0)
           n
           (iter (cdr ls0) (+ (car ls0) n))))))
    (iter ls 0)))

; 3  將一個代表正整數的字串轉化為對應整數。
(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)))

do

不常用,但 do 也可以處理 looping,語法如下:

(do binds (predicate value)
    body)

變數在 binds 部份被綁定,如果 predicate 為 #t,則函數由循環中 escape,並回傳 value,否則繼續 looping

binds 的格式如下,變量p1p2,…被分別初始化為i1i2,…並在循環後分別被更新為u1u2,…。

[binds] → ((p1 i1 u1) (p2 i2 u2) ... )

ex:

; 變數n1和p分別被初始化為n和n,在每次循環後,分別被 減去1 和 乘以(n1 - 1)。當n1變為1時,函數返回p。
(define (fact-do n)
  (do ((n1 n (- n1 1)) (p n (* p (- n1 1)))) ((= n1 1) p)))
; 1  翻轉 list 元素的順序
(define (my-reverse-do ls)
  (do ((ls0 ls (cdr ls0))  (ls1 () (cons (car ls0) ls1)))
      ((null? ls0) ls1)))

; 2  加總 list
(define (my-sum-do ls)
  (do ((ls0 ls (cdr ls0))  (n 0 (+ n (car ls0))))
      ((null? ls0) n)))

; 3  將一個代表正整數的字串轉化為對應整數。
(define (my-string->integer-do str)
  (do ((ls0 (string->list str) (cdr ls0))
       (n 0 (+ (- (char->integer (car ls0)) 48)
         (* n 10))))
      ((null? ls0) n)))

通常來說,named let 用於簡單的循環,而letrec則是用來寫複雜的局部遞歸函數。

高階函數 higher order function

高階函數 higher order function 是一種以函數為參數的函數,用於 mapping, filtering, folding, sorting list。高階函數增加了程式的模組特性。例如使用高階函數實作 sorting,可將排序條件與過程分離。

例如 sort 有兩個參數:一個是待排序的 list,一個是 Ordering function

(sort '(7883 9099 6729 2828 7754 4179 5340 2644 2958 2239) <)
;Value 12: (2239 2644 2828 2958 4179 5340 6729 7754 7883 9099)

; 改以數字末兩位排序
(sort '(7883 9099 6729 2828 7754 4179 5340 2644 2958 2239)
      (lambda (x y) (< (modulo x 100) (modulo y 100))))
;Value 13: (2828 6729 2239 5340 2644 7754 2958 4179 7883 9099)

映射 Mapping

map

procedure是個與某個過程或lambda表達式相綁定的符號。作為參數的表的個數,視procedure需要的參數而定。

(map procedure list1 list2 ...)

ex:

; Adding each item of '(1 2 3) and '(4 5 6).
(map + '(1 2 3) '(4 5 6))
;Value 14: (5 7 9)

; Squaring each item of '(1 2 3)
(map (lambda (x) (* x x)) '(1 2 3))
;Value 15: (1 4 9)
for-each

for-each的格式與map一致。但for-each並不返回一個具體的值,只是用於副作用。

ex:

(define sum 0)

(for-each (lambda (x) (set! sum (+ sum x))) '(1 2 3 4))

sum
;Value: 10

ex: 將 list 裡所有元素 *2

(define (double list)
    (map (lambda (x) (* x 2)) list) )

(double '(1 2 3))
;Value 16: (2 4 6)

(double (list 1 2 3))
;Value 17: (2 4 6)

ex: 將兩個表中對應位置元素相減的函數

(define (minus list1 list2)
    (map - list1 list2) )

(minus '(1 2 3) '(4 5 6))
;Value 18: (-3 -3 -3)

filtering

R5RS 沒有定義 filtering 函數,但 scheme 提供了 keep-matching-items 與 delete-matching-item

(keep-matching-items '(1 2 -3 -4 5) positive?)
;Value 19: (1 2 5)

ex:

; 過濾出偶數
(keep-matching-items '(1 2 -3 -4 5) (lambda (x) (= (modulo x 2) 0)))
;Value 20: (2 -4)

; 濾出 不滿足10 ≤ x ≤ 100 的數
(keep-matching-items '(1 10 20 50 100 150) (lambda (x) (not (<= 10 x 100))))
;Value 23: (1 150)

Folding

R5RS 沒有定義 folding 函數,但 scheme 提供了 reduce

(reduce + 0 '(1 2 3 4))                 ;⇒  10
(reduce + 0 '(1 2))                     ;⇒  3
(reduce + 0 '(1))                       ;⇒  1
(reduce + 0 '())                        ;⇒  0
(reduce + 0 '(foo))                     ;⇒  foo
(reduce list '() '(1 2 3 4))            ;⇒  (4 (3 (2 1)))

ex: 撰寫將表中所有元素平方的函數,然後求取它們的和,最後求和的平方根

(define (fun list)
    (sqrt (reduce + 0 (map (lambda (x) (* x x)) list))))

(fun '(3 4))
;Value: 5

Sorting

R5RS中沒有定義排序函數,但 scheme 提供了 sort (merge-sort 實作) 與 quick-sort

(sort '(3 5 1 4 -1) <)
;Value 26: (-1 1 3 4 5)

ex:

; 以sin(x)的大小升序排序
(define (sort-sin ls)
  (sort ls (lambda (x y) (< (sin x) (sin y)))))

; 以list長度降序排序
(define (sort-length ls)
  (sort ls (lambda (x y) (> (length x) (length y)))))

apply

將一個過程應用於一個表(將表展開,作為過程的參數),函數可有多個參數,但首參數和末參數分別應該是一個過程和一個表

(apply max '(1 3 2))      ;⇒   3
(apply + 1 2 '(3 4 5))    ;⇒  15
(apply - 100 '(5 12 17))  ;⇒  66

ex: 撰寫將表中所有元素平方的函數,然後求取它們的和,最後求和的平方根

(define (sqrt-sum-sq-a ls)
  (sqrt (apply + (map (lambda (x) (* x x)) ls))))

編寫高階函數

member-if, member

member-if, member

member-if函數使用一個謂詞和一個表作為參數,返回一個子表,該子表的car部分即是原列表中首個滿足該謂詞的元素。

(define (member-if proc ls)
  (cond
   ((null? ls) #f)
   ((proc (car ls)) ls)
   (else (member-if proc (cdr ls)))))

(member-if positive? '(0 -1 -2 3 5 -7))
;⇒  (3 5 -7)

member函數檢查特定元素是否在表中,使用三個參數,其一為用於比較的函數,其二為特定項,其三為待查找表。

(define (member proc obj ls)
  (cond
   ((null? ls) #f)
   ((proc obj (car ls)) ls)
   (else (member proc obj (cdr ls)))))

(member string=? "hello" '("hi" "guys" "bye" "hello" "see you"))
;⇒  ("hello" "see you")

References

mit-scheme user doc

Yet Another Scheme Tutorial 中文版

Yet Another Scheme Tutorial

沒有留言:

張貼留言