PowerPoint プレゼンテーション

10. 知識(履歴)の蓄積
プログラミング論 I
本日の内容
• 知識(履歴)の蓄積(関数の accumulator-style 化)
– 構造再帰での問題例：
• 相対距離のリスト→絶対距離のリスト
• リスト中の数の和
• 木の高さ
知識(履歴)の損失
関数：文脈独立
• 単独、あるいは再帰中での呼び出しであっても同じに機
能する(同じ引数なら同じ結果を返す)
文脈独立性は利点でもあるが、時にはそうでない。
• 再帰的な評価の間の履歴を覚えていない。
– 時に構造再帰関数を複雑,低効率にする
– 時に生成的再帰に破滅的欠陥をもたらす
⇒追加引数(accumulator)により知識(履歴)を蓄積し解決
Accumulator スタイルの関数を設計する
関数の accumulator-style 化
万能の決定的方法はないが指針はある：
1. accumulator-style が有益か、または必要かを認識：
• 構造再帰の場合で、再帰の結果を再帰的な補助
関数により処理 → accumulator の導入を考慮
• 生成的再帰の場合で、履歴なしでは結果を生成
し損ねる可能性がある場合 (判断は容易でない)
2. その場合 accumulator が何を表すか理解し定式化
ここでは比較的容易な標準的構造再帰関数を例題に
accumulator 付補助関数を使う関数に変換。
例題1.相対距離リスト→絶対距離リスト
各数が左隣接点(最初は原点)からの距離を表す、相対距
離のリストから、原点からの絶対距離のリストを計算
例：入力 (list 50 40 70 30 30)
原点
50
40
70
30
30
190
220
出力 (list 50 90 160 190 220)
原点
50
90
160
構造的再帰：リスト alonの尾部への再帰が正しく機能する
(尾部に関する絶対距離のリストを返す)として、リスト alon
の先頭を結果の先頭に追加し, また尾部の各要素に加算
例題1.相対距離リスト→絶対距離リスト
;; rela2abs: (listof number) -> (listof number)
;; to convert a list of relative distances to a list of
;; absolute distances ( the first item on the list
;; represents the distance to the origin
(define (rela2abs alon)
(cond
相対値の先頭を絶対値の
[(empty? alon) empty] 先頭としてリストに追加
[else
尾部への再帰は部
(cons (first alon)
分的な結果を返す
(add-to-each (first alon)
(rela2abs (rest alon)) ))]))
相対値の先頭を尾部の絶
対値リストの各要素に加算
;; add-to-each: number (listof number) -> (listof number)
;; to add n to each number on alon
(define (add-to-each n alon)
(cond
[(empty? alon) empty]
[else (cons (+ (first alon) n)
(add-to-each n (rest alon)))]))
例題1.相対距離リスト→絶対距離リスト
add-to-each
原点
原点
50
50
40
+50
40
70
30
30
+70
+40 +40
+50 +50
70 30
+30
+70
+40
+50
30
呼出による
加算回数
1
...
N-2
N–1
合計
原点
50
90
160
190
220
N 1
i
1
例題1.相対距離リスト→絶対距離リスト
次の評価を考えると、問題サイズNを増やすにつれ必要時
間は問題サイズNより大きく増加：
(rela-2-abs (list 0 ... N))
例：N=100から200に増やすと時間は2倍でなく4倍。
問題の単純さの割に「仕事」の量は膨大
改善例：相対距離のリストをたどりながら絶対距離を計算
「知識(履歴)」の損失を防ぐ追加引数：accum
• 累積距離を表し相対距離を絶対距離に変換するとき使う
• 最初の値は 0、リストの要素を処理するとき、履歴を蓄積
例題1.相対距離リスト→絶対距離リスト
(define (rel2abs-a alon accum)
第2引数(accumulator)は
(cond
[(empty? alon) empty] 第1引数現在の点の絶対距離
はリスト
[else
(cons (+ (first alon) accum)
(rel2abs-a (rest alon)
(+ (first alon) accum)))]))
accumulator がどう計算過程を単純化するか示す評価例：
(rel2abs-a (list 3 2 7) 0)
= (cons 3 (rel2abs-a (list 2 7) 3))
= (cons 3 (cons 5 (rel2abs-a (list 7) 5)))
= (cons 3 (cons 5 (cons 12 (rel2abs-a empty 12))))
= (cons 3 (cons 5 (cons 12 empty))) = (list 3 5 12)
リストの各項目が処理されるのは1度 → N項目のリストに
対しオーダーNの自然再帰ステップを実行
例題1.相対距離リスト→絶対距離リスト
新しい関数 rel2abs-a の小さな問題
• accumulatorは性能(中身)を改善するが使用法を変える
– 引数が2つで,もとの関数 rela2abs と異なる
– 正しい初期値を指定する必要がある(今回は 0 )
局所定義に rel2abs-aを含む関数定義を使い解決：
(define (rela2abs2 alon)
(local ((define (rel2abs-a alon accum)
(cond
[(empty? alon) empty]
[else
(cons (+ (first alon) accum)
(rel2abs-a (rest alon)
(+ (first alon) accum)))])))
(rel2abs-a alon 0)))
例題2. 関数sumの accumulator-style 化
;; sum : (listof number) -> number
;; to compute the sum of the numbers on alon
(define (sum alon)
(cond
[(empty? alon) 0]
[else (+ (first alon) (sum (rest alon)))]))
上記関数を下記テンプレートでaccumulator-style化する
追加引数accum
(define (sum alon0)
(accumulator)は
(local (;; accumulator is …
(define (sum-a alon accum) 何を表すか?
(cond
[(empty? alon) …] リストの最後まできたら?
[else
再帰時にaccumを …(sum-a (rest alon)
どうすべきか？
… (first alon) … accum)) …])))
(sum-a alon0 …))) accum の初期値は?
例題2.関数sumの accumulator-style 化
;; sum : (listof number) -> number
;; to compute the sum of the numbers on alon0
(define (sum alon0)
(local (;; accum is the sum of the numbers that
;; preceded those in alon on alon0
(define (sum-a alon accum) 追加引数 accumは
alon0上での alon
(cond
より前の数の計
[(empty? alon) accum]
リストの最後まできたらaccumが答
再帰時にaccumに [else
現在の先頭要素 (sum-a (rest alon)
の値を加える
(+ (first alon) accum))])))
(sum-a alon0 0)))
accum の初期値は0
練習1．階乗関数の accumulator-style 化
以下は階乗を求める構造的再帰関数である。
;; ! : N -> N
;; to compute n * (n-1) * ... * 2 * 1
(define (! n)
(cond
[(zero? n) 1]
[else (* n (! (sub1 n)))]))
これを下記テンプレートでaccumulator-style化せよ。
(define (! n0)
(local (;; accum …
(define (!-a n accum)
(cond
[(zero? n) …]
[else
… (!-a (sub1 n) … n … accum) …])))
(!-a n0 …)))
例題3. 木構造の高さ
木構造の高さ(根から葉までの枝の数)を計算
木構造：
–
–
–
概念的には節(node)と枝(branch)からできている。
つながっている節と節で、根に近いものを親、そう
でないものを子という。
ある節から別の節への枝の道が1通りしかない。
親
節点(node)
枝(branch)
子
単純な木構造
木構造
根(root)
葉(leaf)
部分木
• 根(root)：木の一番上の節点(自然界の木とは上下反対)
• 葉(leaf)：子を持たない節点
• 部分木：木の中のある節点を相対的な根と考えたとき
の，そこから子の方向にある枝と節点の集合
二分木(binary tree)
各節点から出る枝が二本以下の木構造
節の構造体定義 (define-struct node (left right))
2分木 tree はいずれか (今回は各節にデータを含まない)
1. empty (子ノードのない leaf 。再帰的なtree定義の基底)
2. 部分木を持つ節を表す構造体 (make-node tleft tright)
ここで tleft, tright は左と右の部分木の tree データで、
セレクタ node-left, node-rightでアクセスされる。この
節と各部分木tleft, trightの間に枝があるとする。
empty
(make-node
(make-node
(make-node
empty empty)
empty
左の子(部分木) 右の子
(make-node
empty
概念的には
empty))
枝がある
empty)
例えばこ
こが対応
例題3. 木構造の高さ
データ定義は2つの場合を持つのでそれを処理する関数も
2つの場合分けのcond式を持つ。非emptyの節は、データ
定義と同様この関数は2つの自己参照(再帰呼出)を持つ。
;; height : tree -> number
;; measure the height of a tree abt
(define (height abt)
(cond
[(empty? abt) 0] emptyで部分木がなければ枝もなく高さ 0
[else (+ 1
(max (height (node-left abt))
(height (node-right abt))))]))
部分木がある場合、今の節との間にある枝の分1と部分
木の高さ(大きいほうを選ぶ) を加えると今の高さになる
例題3. 木構造の高さ
前述の関数heightを accumulator スタイルに変換する。
適切なテンプレートをlocal式定義中にまず置く：
(define (height abt0)
(local (;; accum ...
(define (height-a abt accum)
(cond
[(empty? abt) ...]
[else
… (height-a (node-left abt) … accum)…
… (height-a (node-right abt) … accum)…
… ])))
(height-a abt0 ...)))
accumulator が表すべき履歴は何か決定する必要
例題3.木構造の高さ
accumulator： height-a が処理した枝の数を表すべき。
– 初期値は0 (まだ処理した枝は0個)；
– 再帰的に子node を処理する際、枝をたどる ⇒ accumulator を +1：
(define (height abt0)
(local (;;accum represents how many nodes height-a
;;has encountered on its way to abt from abt0
(define (height-a abt accum)
(cond
[(empty? abt) …]
[else
…(height-a (node-left abt) (+ accum 1)) …
…(height-a (node-right abt) (+ accum 1))
…])))
(height-a abt0 0))
例題3.木構造の高さ
accumulator：rootからleafへの経路上の height-a の再帰数
– 基底ケースの結果は accumulatorの値(=高さ(枝の数))
• けれども、それは最終の結果ではなく候補。2番目のcond節
で、左右の部分木の高さの大きい方を選択(max演算を使う)
(define (height abt0)
(local (;;accum represents how many nodes height-a
;;has encountered on its way to abt from abt0
(define (height-a abt accum)
(cond
[(empty? abt) accum]
[else (max (height-a (node-left abt)
(+ accum 1))
(height-a (node-right abt)
(+ accum 1)))])))
(height-a abt0 0)))
練習2. 節に値を持つ二分木
木には様々な種類：内部の節が数値データを持つ二分木の例
節の構造体定義が (define-struct node (val left right)) の
とき二分木 tree は次のいずれかである
1. empty ;;節でなく葉の場合。再帰的なtree定義の基底
2. (make-node v tl tr) ;;数値vを持つ節．ここで tl,trはnode型の部分木
このとき以下を求めるプログラムを作成せよ．
(アキュムレータを使わないものと使うものを考えよ)．
1. 木の節に含まれる値の合計
2. 根から葉に至る経路中の値の和のうち，最大のものを求める
木の例： (make-node
empty
(make-node
63
63
;節の値
(make-node
29
empty ;左部分木
empty
empty);右部分木
(make-node
89
empty
empty))
empty)
参考：二分木の構築例(節データの追加)
;; add-node : node number -> node
(define (add-node tree val)
(cond
[(empty? tree) (make-node val empty empty)]
[else
(cond
[(= (node-val tree) val) tree] ;;この版では同じ値のvalが
;;存在する場合は追加しない．
[(> (node-val tree) val)
(make-node (node-val tree)
(add-node (node-left tree) val)
(node-right tree))]
[else
(make-node (node-val tree)
(node-left tree)
(add-node (node-right tree) val))])]))
このプログラムを使うと，ある節の左の部分木中の全ての節の値が，
その節の値より小さく，右の部分木中の全ての節の値が，その節の
値より大きいような二分木(二分探索木 binary search tree) ができる
課題
課題. invert のAccumulator-style化
リストの要素を逆順にしたリストを返す以下の関数 invert
をAccumulator-style化せよ。
;; invert : (listof X) -> (listof X)
;; to construct the reverse of alox
(define (invert alox)
(cond
[(empty? alox) empty]
[else
(make-last-item (first alox)
(invert (rest alox)))]))
再帰の結果をまた再帰的な補助関数で処理している
;; make-last-item : X (listof X) -> (listof X)
;; to add an-x to the end of alox
(define (make-last-item x alox)
(cond
[(empty? alox) (list x)]
[else (cons (first alox)
(make-last-item x (rest alox)))]))

Download Report