8. 高階関数を用いた抽象化 プログラミング論I.

Presentation on theme: "8. 高階関数を用いた抽象化 プログラミング論I."— Presentation transcript:

1 8. 高階関数を用いた抽象化 プログラミング論I

2 今日の内容 主要トピックス：高階関数とその利用による抽象化 副次的トピックス： 局所定義(local式)、近似値 例題
数列と級数　series べき級数 power_series テーラー級数　 指数関数のテーラー展開 taylor-exp　 台形則による数値積分 trapezoid

3 高階関数とは? 入力や結果が関数である関数(関数も値)
例：第7回の filter1 や map も入力が関数(または演算子)であり，高階関数． 計算の基本原理は従来同様，置換(substitution)による． 例えば関数呼出(適用)のとき： 関数適用の部分は，関数定義の本体式に置換される (式中のパラメータに対応する変数は，実際の値で置き換える) パラメータの値が関数や演算子でも，その値で置換して計算する． これにより新たな関数適用式が生じれば，上記を繰返す．

4 例題1. 数列と級数 - 数列 - 数列を，項番号に相当する自然数を受け取り，数を返す関数として実現する．
例：自然数の偶数，奇数の第 i 項 (i>=0)を計算する． ;; make-even : N -> N[even] ;; to compute the i-th even number (define (make-even i) (* 2 i)) ;; make-odd : N -> N[odd] ;; to compute the i-th odd number (define (make-odd i) (+ (* 2 i) 1))

5 make_even, make_odd #include <stdio.h> int make_even(int); int make_odd(int); void main(){ printf("make-even(2):%d\n", make_even(2)); printf("make-odd(2):%d\n", make_odd(2)); } int make_even(int i){ return (2 * i); int make_odd(int i){ return (2 * i + 1); // プロトタイプ宣言

6 例題1. 数列と級数 級数：数列の合計 make-even (make-odd) を使い，初項(第0項)から第n項までの，奇数(偶数)を合計する関数： これら2つの関数は，抽象化の対象 ;; series-even : N -> number ;; to sum up the first n even numbers (define (series-even n) (cond [(= n 0) (make-even n)] [else (+ (make-even n) (series-even (- n 1)))])) ;; series-odd : N -> number ;; to sum up the first n odd numbers (define (series-odd n) (cond [(= n 0) (make-odd n)] [else (+ (make-odd n) (series-odd (- n 1)))]))

7 make_even, make_odd #include <stdio.h> int make_even(int i){ return (2 * i); } int make_odd(int i) { return (2 * i + 1);} int series_even(int n){ if (n == 0) return make_even(n); else return make_even(n) + series_even(n-1); } int series_odd(int n){ if (n == 0) return make_odd(n); else return make_odd(n) + series_odd(n-1); void main(){ printf("series-even(2):%d\n", series_even(2)); // 6 printf("series-odd(2):%d\n", series_odd(2)); // 9

8 例題1. 数列と級数 レシピにしたがって抽象化 ;;series : N (N -> number) -> number
;;sum up the first n numbers in the sequence a_term (define (series n a_term) (cond [(= n 0) (a_term n)] [else (+ (a_term n) (series (- n 1) a_term))])) series は級数(数列の合計)を求める高階関数: 第1引数は上限項の番号，第2引数は数列の関数．数列の第 i項が (f i) のとき自然数 n と f から (f 0) (f 1) … (f n) の和を再帰的に計算 (注:seriesの定義中では fは a_term)

9 関数へのポインタ 引数の数と型，返値を 合わせる
#include <stdio.h> int make_even(int i) { return (2 * i); } int make_odd(int i) { return (2 * i + 1);} int series_even(int n){ if (n == 0) return make_even(n); else return make_even(n) + series_even(n - 1); } int series_odd(int n){ if (n == 0) return make_odd(n); else return make_odd(n) + series_odd(n - 1); int series(int n, int(*a_term)(int i)) { if (n == 0) return (*a_term)(n); else return (*a_term)(n)+series(n - 1, (* a_term)); void main(){ printf("series-even(2):%d\n", series(2, make_even)); printf("series-odd(2):%d\n“ , series(2, make_odd));

10 例題1. 数列と級数 (series) 入力は1つの 自然数 n と1 出力は数。 f に つの関数 f よる数列の和 series
例：4 make-even = 20 make-even と make-odd に適用： ;; series-even1 : N -> number (define (series-even1 n) (series n make-even)) ;; series-odd1 : N -> number (define (series-odd1 n) (series n make-odd))

11 (series 4 make-even) の計算過程の概略
= … = (+ (make-even 4) (series 3 make-even)) = (+ (make-even 4) (+ (make-even 3) (series 2 make-even))) = (+ 8 (+ 6 (+ 4 (+ 2 0)))) = 20 最初の式 実行結果

12 練習1. 数列と級数 自然数の i 番目の3の倍数を計算する関数 triplesを定義せよ．
次に高階関数 seriesを使い n 番目までの3の倍数の和を求める関数series-triplesを定義せよ．

13 定義の局所化(local式) 複雑な処理をするプログラムは複雑になる傾向 → プログラムに構造を与えるのが有効
複雑な処理をするプログラムは複雑になる傾向 → プログラムに構造を与えるのが有効 local式：関連する任意数の定義をカプセル化する式 local式は文法的には単に式の1つの種類： <exp> = (local (<def-1> ... <def-n>) <exp>) キーワード local， 括弧で囲まれた定義の並び，本体式 本体式の評価のための変数，関数，構造体を定義する．local式の外では，その定義は効果を持たない． 例： (local ((define (f x) exp-1)) exp) expの評価中有効な関数fを定義．expの結果がlocal式の結果． 例： (local ((define PI 3)) exp) exp の評価の間，一時的に変数PIが3を表す．

14 例 (define PI 3.14) ;; area-of-disk : number -> number ;; compute the area of a disk whose radius is r ;; considering the size of r (define (area-of-disk r) (local ((define (disk-area r pi) (* pi r r)) (define (yutori r) (local ((define PI 3)) (disk-area r PI))) (define (special r) (local ((define PI )) (define (normal r) (cond [(<= r 10) (yutori r)] [(<= r 100) (normal r)] [else (special r)]))) 名前の衝突を気にしなくて良い

15 定義の局所化：local式とスコープ 定義の有効範囲を定める構文範囲 (スコープ) に注意 対応する定義をまず同一スコープ内で探し，なければ
定義の有効範囲を定める構文範囲　(スコープ)　に注意 対応する定義をまず同一スコープ内で探し，なければ 順次，内側から外側の順にスコープを広げて探す． (define (h z) (local ((define (f x) (+ x z)) (define (g alon) (cond [(empty? alon) empty] [else (cons (f (first alon)) (g (rest alon)))]))) (g (list 1 2 3))) ) DrRacketでは「Check Syntax」 機能で対応が表示できる 上記の関数 h を使った (h 10) の結果は? z は同一スコープ内には なく外側の関数の引数 f は同一スコープ内になくlocal式内の隣の局所定義 g はlocal式で局所的に定義

16 (h 10) (h 10) ->(g (list 1 2 3)) ->(cons (f 1) (g (list 2 3))) ->(cons (+ 1 10) (cons (f 2) (g (list 3)))) ->(cons 11 (cons (+ 2 10) (cons (f 3) (g empty)))) (cons 12 (cons (+ 3 10) empty))) ->(list )

17 練習2. local式 以下の結果を求めよ a) (define PI 3.14) (list (* PI 10 10))
b) (local ((define PI 3)) (* PI 10 10)) c) (define PI 3.14) (list (* PI 10 10) (local ((define PI 3)) (* PI 10 10)))

18 例題2. べき級数 べき級数 を求める高階関数power_series
自然数 n,　数 x, 関数 g から (* (g 0)(expt x 0)) + (* (g 1)(expt x 1)) + …+ (* (g n)(expt x n)) を求める n = 0 の時 n > 0 の時 例題1のseriesを補助関数として使う

19 例題2. べき級数 べき級数を求める高階関数 power_series 例題1のseriesを補助関数として使う
何が同じで何が違うか(ともに n > 0 のとき) series でやりたい計算 power_series でやりたい計算 各項 g(n)の計算の際，x の n 乗も掛け合わせる power_seriesの定義中で上記の項計算をするには? f(n)=g(n)*xn gとxを，引数として与える

20 例題2. べき級数 power_series 関数
;;power_series: number N (N -> number) -> number (define (power_series x n ｇ) (local ((define (power_term i) (* (ｇ i) (expt x i)))) (series n power_term) ) ) べき級数の第i項は数列の第i項に x の i 乗を掛けたもの ⇒ そのような項の計算をする関数 power_term を局所的に定義 各項の和(級数)を求める手順はseries を利用 power_term(i)=g(i)*xi gとxは引数として与えられる power_termは前スライドの f に対応

21 C言語は，関数内関数は書けないので，seriesと同じように書く
power_series C言語は，関数内関数は書けないので，seriesと同じように書く #include <stdio.h> #include <math.h> double series(int n, double(*a_term)(int i)){ if (n == 0) return (*a_term)(n); else return (*a_term)(n)+series(n - 1, (* a_term)); } // power_series: double, int, (double -> double)->double double power_series(double x, int n, double(*g)(double)){ if (n == 0) return (*g)(n) * pow(x, n); else return (*g)(n) * pow(x, n) + power_series(x, n-1, (*g)); double g1(double k){ return k; }; void main(){ printf("power_series(2, 3, g1):%f\n", power_series(2, 3, g1));

22 べき級数 power_series の計算例(概略)
power_series を使い簡単なべき級数 x + 2x2 +…+ nxn を計算 (power_series 2 3 g1) = (local ((define (power_term i) (* (g1 i) (expt 2 i)))) (series 3 power_term)) (+ (power_term 3) (series 2 power_term)))) = … (+ (power_term 3) (+ (power_term 2) (+ (power_term 1) (power_term 0))))) = (+ (* (g1 3)(expt 2 3)) (+ (* (g1 2)(expt 2 2)) (+ (* (g1 1)(expt 2 1)) (* (g1 0)(expt 2 0))))) = (+ 24 (+ 8 (+ 2 0))) = ... = 34 最初の式 但し x=2, (define (g1 k) k) 実行結果

23 練習3. べき級数 power_series を使ったべき級数 x + 22x2 +…+ n2xn について考える。 (define (g2 k) (* k k)) として(power_series 2 3 g2)の計算の概略示せ。また (power_series 3 4 g2) の結果を求めよ。

24 限定値(近似値) 注意：近似値での計算を繰り返すと誤差が累積! 計算機で表現可能な値は大きさ，精度とも限界がある．
通常は(exactな)確定値を計算しようとするが，結果が #iが付いた(inexactな)限定値(近似値)になる場合がある もともと sin, cos, log 等の値は，近似値でしか得られない 例：(sin 0.1) を実行すると → #i 意図的に(結果の見易さなどのため) #i を付け近似値を計算 例：(expt ) と (expt #i11 200) を比べてみる ここで (expt #i11 200) = #i e+208 の e+208 は 10 の 208 乗の意味，つまり e+208 = × 10208 また 1.23e-5 = 1.23 × 10-5 = 注意：近似値での計算を繰り返すと誤差が累積!

25 テーラー展開 テーラー展開：関数 f が，a の近傍で定義されていて，点 a で n 階微分可能であるとき

26 テーラー展開(例) 収束半径：∞ 収束半径：∞ 収束半径：∞ 収束半径：１ 収束半径：１

27 例題3. テーラー展開 -指数関数- 例題2の power_series を使って指数関数のテーラー展開式にもとづいた ex の近似値を求める関数 taylor-exp (入力は1つの数値 x)を定義する． (展開は第10 項までとする) べき乗にかかる係数は (define (exp_term i) (/ 1 (! i)))

28 例題3. テーラー展開 -指数関数- べき級数 指数関数の第 i 係数項 k の階乗の関数! ex を計算 (10項までの近似)
(define (series n a_term) (cond [(= n 0) (a_term n)] [else (+ (a_term n) (series (- n 1) a_term))])) ;; (define (power_series x n term) (local ((define (power_term i) (* (term i) (expt x i)))) (series n power_term))) (define (exp_term i) (/ 1 (! i))) (define (! k) (cond [(= k 0) 1] [else (* k (! (- k 1)))])) (define (taylor-exp x) (power_series x 10 exp_term)) べき級数 指数関数の第 i 係数項 k の階乗の関数! ex を計算 (10項までの近似)

29 e^x (taylor級数) #include <stdio.h> #include <math.h> double series(int n, double(*a_term)(int i)){ if (n == 0) return (*a_term)(n); else return (*a_term)(n)+series(n - 1, (* a_term)); } // power_series: double, int, (double -> double)->double double power_series(double x, int n, double(*g)(double)){ if (n == 0) return (*g)(n) * pow(x, n); else return (*g)(n) * pow(x, n) + power_series(x, n-1, (*g)); // factorial: double -> double // k!の計算 double factorial(double k){ if ((int) k == 0) return 1; else return k * factorial(k - 1); // exp_term: double -> double // 1/k!の計算 double exp_term(double k){ return 1 / factorial(k); } void main(){ // e^1を10項まで計算 printf("taylor_exp(1):%f\n", power_series(1, 10, exp_term)); //

30 参考：taylor-exp での誤差 (define (taylor-exp x)
(power_series x 10 exp_term)) x10/10! の項まで計算 誤差：x11/11! 以降 taylor級数第10項までの計算→ 近いけれども… 数値の先頭に #i → 限定的(inexact)表現(近似値)

31 練習4. cos 関数のテーラー展開 例題3のpower_seriesを使い，cos 関数のテーラー展開式にもとづいた cos(x) の近似値を求める関数 taylor-cos (入力は1つの数値 x)を定義せよ． (展開は第10 項までとする) 初項は第0項，奇数項の値は 0 と考える k を i で割った余りは (remainder k i)

32 cos ;; cos_term: number -> number ;;(* (cos_term i) (expt x i)) (define (cos_term i) (cond [(= (remainder i 4) 0) (/ 1 (! i))] [(= (remainder i 2) 0) (/ -1 (! i))] [else 0])) (define (taylor_cos x) (power_series x 10 cos_term)) ;; (taylor_cos 0.3)

33 cos_term double cos_term(double i){ if ((int)i%4 == 0) return 1 / factorial(i); else if ((int)i%2 == 0) return -1 / factorial(i); else return 0; } void main(){ printf("%f (%f) \n", power_series(0.3, 10, cos_term), cos(0.3));

34 例題4. 数値積分 連続関数 f, x軸, x=a, x=b (区間 [a, b])で囲まれた面積 定積分： 式の変形による関数の積分
⇒　ごく限られた関数しか定積分できない 「数値積分」が重要 ⇒　高階関数，級数の考えを使い，台形則による数値積分関数 trapezoid を作る 入力は被積分関数 f と3つの数値(積分区 間の両端の x 座標a, b, 区間分割数 n) trapezoid 出力は数値

35 台形則による数値積分 区間［a，b］を n 等分 (1区間の幅 h = (b - a) / n ) し， n 個の台形を考え, その面積の和 Sn で定積分 I を近似する． f(x) が連続関数のとき，n → ∞で，Sn → I となる 但し，単に「n を大きくする」のも問題 計算時間の問題，丸め誤差の問題などが発生 f(x) x0 = a xn = b x x1 x2 xn-1 x3 xn-2 但し，x0 = a, xi = x0 + i × h

36 例題4. 数値積分 trapezoid 例題1の series を再利用した trapezoid
;;trapezoid:(number -> number) number number N -> number ;;to compute the area under the graph of f between a & b (define (trapezoid f a b n) (local ((define h (/ (- b a) n)) (define (term i) (* (/ h 2) (+ (f (+ a (* h i))) (f (+ a (* h (+ i 1)))))))) (series (- n 1) term)))

37 trapezoid double trapezoid(double(*g)(double), int a, int b, int n){ double h = (double)(b - a) / n; double sum = 0; for (int i = 0; i < n; i++) sum += (h / 2)*((*g)(a + (h*i))+ (*g)(a + (h*(i+1)))); return sum; } double f(double x){ return x*x; } void main(){ printf(“trapezoid:%f\n”, trapezoid(f, 0, 1, 100)); (series (- n 1) term) term

38 課題

39 課題1. テーラー展開 例題3 を参考に以下の2つのテーラー展開の値を求める関数を作成せよ． even? (偶数ならば true)を使うこと

40 sin_term, atan_term (define (sin_term n) (cond [(= (remainder n 4) 1) (/ 1 (! n))] [(= (remainder n 4) 3) (/ -1 (! n))] [else 0])) ;; (define (atan_term n) [(= (remainder n 4) 1) (/ 1 n)] [(= (remainder n 4) 3) (/ -1 n)] (define (taylor_sin x) (power_series x 10 sin_term)) (define (taylor_atan x) (power_series x 100 atan_term))