PowerPoint プレゼンテーション

今日の内容

高階関数

関数を値として扱う



関数を引数にとる
関数を返す関数
プログラミングの例題

クイックソート
関数を値と扱う

関数を引数にとれる

(define (f x) (x 10))



(define (f ｇ) (ｇ 10))
(f add1)
関数を値とする



(define (g x) add1)
g はadd1という関数を返す
（注意：この場合xは使われていない）
温度CからFへの変換
;; convertCF : lon -> lon
摂氏(Celsius, ℃)
華氏（Fahrenheit, °F)
(define (convertCF alon)
F = 9/5 * C + 32
(cond
[(empty? alon) empty]
[else
(cons (C->F (first alon))
(convertCF (rest alon)))]))
関数C->F は自分で定義すること．
在庫品(inventory-record)


在庫品は構造体として次のように定義する．
(def-struct IR (name nitems price)



name は品名（シンボル）
nitemsはこの在庫品の在庫量（数）
priceは価格（数）
在庫品目名リスト
;; names : loIR -> los
(define (names aloIR)
(cond
[(empty? aloIR) empty]
[else
(cons (IR-name (first aloIR))
(names (rest aloIR)))]))
プログラムの比較１
(define (convertCF alon)
(define (names aloIR)
(cond
(cond
[(empty? alon) empty]
[(empty? aloIR) empty]
[else
[else
(cons (C->F (first alon))
(cons (IR-name (first
aloIR))
(convertCF (rest
alon)))]))
(names (rest
aloIR)))]))
プログラムの比較２
(define (convertCF Ｇ alon)
(cond
[(empty? alon) empty]
[else
(cons (Ｇ (first alon))
(convertCF Ｇ (rest
alon)))]))
(define (names Ｇ aloIR)
(cond
[(empty? aloIR) empty]
[else
(cons (Ｇ (first aloIR))
(names Ｇ (rest
aloIR)))]))
プログラムの比較 3
(define (convertCF Ｇ x)
(cond
[(empty? x) empty]
[else
(cons (Ｇ (first x))
(convertCF Ｇ (rest
x)))]))
(define (names Ｇ x)
(cond
[(empty? x) empty]
[else
(cons (Ｇ (first x))
(names Ｇ (rest x)))]))
プログラムの比較 4
(define (g Ｇ x)
(cond
[(empty? x) empty]
[else
(cons (Ｇ (first x))
(g Ｇ (rest x)))]))
(define (names Ｇ x)
(cond
[(empty? x) empty]
[else
(cons (Ｇ (first x))
(names Ｇ (rest x)))]))
map
(define (map f x)
(cond
[(empty? x) empty]
[else (cons (f (first x))
(map f (rest x)))]))
Mapを用いた再定義
;; convertCF-from-map : lon -> lon
(define (convertCF-from-map alon)
(map C->F alon))
;; names-from-map : loIR -> los
(define (names-from-map aloIR)
(map IR-name aloIR))
多相型(polymorphism)


map : (number -> number) (listof number) -> (listof
number)
map : (IR -> symbol) (listof IR) -> (listof symbol)

f : X -> Y

map : (X -> Y) (listof X) -> (listof Y)
Filter (my-filter)
(define (my-filter rel-op alon t)
(cond
[(empty? alon) empty]
[(rel-op (first alon) t)
(cons (first alon)
(my-filter rel-op (rest alon) t))]
[else
(my-filter rel-op (rest alon) t)]))
Filter (my-filter)

(define (my-filter rel-op alon t) .... )

;; (rel-op elem t) がtrueになる要素をリストalonから
;; 取り出し，新たなリストを作る


(my-filter > (list 3 -1 0 5 6 3) 0) =>


(my-filter >= (list 3 -1 0 5 6 3) 0) =>


(list 3 5 6 3)
(list 3 0 5 6 3)
(my-filter eq? (list 2 5 3 8 6 3) 3) =>

(list 3 3)
Filter(my-filter)を使う例： find
;; find : (listof IR) symbol -> (listof IR)
(define (find aloir t)
(define (eq-IR? ir p)
(symbol=? (IR-name ir) p)
(my-filter eq-IR? aloir t))
ラムダ式

関数を表す表現

<exp> :：= … | (lambda (<var> ... <var>) <exp>)




(lambda (x y) (+ (* x x) (* y y)))
(lambda (x) x)
(lambda (x y) x)
(lambda (x y) (x y y))
ラムダ式の例



(lambda (x c) (> (* x x) c))
(lambda (ir p) (< (IR-price ir) p))
(lambda (ir p) (symbol=? (IR-name ir) p))
例


((lambda (x y) (+ (* x y) 3)) 1 2)
((lambda (f x) (f x x)) + 10)
Quick sortの作成：ラムダ式を使う例
;; quick-sort : (listof number) -> (listof number)
;; to create a list of numbers with the same numbers as
;; alon sorted in ascending order
(define (quick-sort alon)
(cond
[(empty? alon) empty]
[else (append
(quick-sort (smaller-items alon (first alon)))
(list (first alon))
(quick-sort (larger-items alon (first alon))))]))
quick-sortの動き









(quick-sort (list 3 4 2 6 5 1))
３を取り出す
3より小さい要素２，１を選び出し(list 2 1)を作る
（quick-sort (list 2 1)) => (list 1 2)
(list 3)を作る
3より大きい要素４，６，５を選び出し (list 4 6 5)を作る
（quick-sort (list 4 6 5)) => (list 4 5 6)
(list 1 2) (list 3)(list 4 5 6)を結合(append)する
(list 1 2 3 4 5 6)
larger-items
;; larger-items : (listof number) number -> (listof number)
;; to create a list with all those numbers on alon
;; that are larger than threshold
(define (larger-items alon threshold)
(cond
[(empty? alon) empty]
[else (if (> (first alon) threshold)
(cons (first alon)
(larger-items (rest alon) threshold))
(larger-items (rest alon) threshold))]))
smaller-items
;; smaller-items : (listof number) number -> (listof number)
;; to create a list with all those numbers on alon
;; that are smaller than threshold
(define (smaller-items alon threshold)
(cond
[(empty? alon) empty]
[else (if (< (first alon) threshold)
(cons (first alon) (smaller-items (rest alon) threshold))
(smaller-items (rest alon) threshold))]))
my-filterを使うと簡単
システム組み込み関数 filter

注意システム組み込み関数 filterがある．

(filter rel-op alist)



rel-opは一引数の述語（真理値を返す関数）
alistはリスト
(filter even? (list 1 2 3))
larger-items, smaller-itemsの再定義
(define (larger-items alon threshold)
(my-filter > alon threshold))
(define (smaller-items alon threshold)
(my-filter < alon threshold))
filterを使ったmy-filterの再定義
(define (my-filter rel-op alon threshold)
(filter
(lambda (x) (rel-op x threshold))
alon))
最初のquick-sortの問題点
(quick-sort (list 3 2 2 5 5 6 1 3 2))
 (list 1 2 2 2 3 3 5 5 6)が答えであってほしい
 (list 2 2 1 2) (list 3) (list 5 5 6)に分割されてし
まう
(quick-sort (list 3 2 2 5 5 6 1 3 2)) => (list 1 2 3
5 6)
 ここで，２，３，５，６がひとつになってしまう
正しいquick-sort
(define (quick-sort alon)
(cond
[(empty? alon) empty]
[else (append
(quick-sort (not-larger-items
(rest alon) (first alon)))
(list (first alon))
(quick-sort (larger-items
(rest alon) (first alon))))]))
not-larger-itemsは自分で定義すること！

Download Report