local variables
用 let 定義 local variable，body由任意多個S-表達式構成，變數的Scope為body，只在body 中有效。
(let binds body)
;binds的格式
[binds] → ((p1 v1) (p2 v2) ...)ex:
(let ((i 1) (j 2))
(+ i j))
;Value: 3let 可以嵌套使用
(let ((i 1))
(let ((j (+ i 2)))
(* i j)))
;Value: 3因變數的作用域僅在body中，下列代碼會產生錯誤，因為在變量j的作用域中沒有變數i的定義。
(let ((i 1) (j (+ i 2)))
(* i j))
;Errorlet*表達式可以用於引用定義在同一個綁定中的變量。實際上，let*只是嵌套的let表達式的 syntax sugar 而已。
(let* ((i 1) (j (+ i 2)))
(* i j))
;Value: 3ex: 計算一元二次方程式的解。它需要三個參數代表係數：a、b、c （ax^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
⇒ 120list 可以用遞迴的方式定義，例如讓 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)
⇒ 120Scheme將尾遞迴轉化為循環，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 的格式如下，變量p1，p2，…被分別初始化為i1，i2，…並在循環後分別被更新為u1，u2，…。
[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: 10ex: 將 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: 5Sorting
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)) ;⇒ 66ex: 撰寫將表中所有元素平方的函數，然後求取它們的和，最後求和的平方根
(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
Yet Another Scheme Tutorial 中文版
沒有留言:
張貼留言