PowerPoint プレゼンテーション

10. 知識(履歴)の蓄積
プログラミング論 I
本日の内容
• 知識(履歴)の蓄積(関数の accumulator-style 化)
– 構造再帰での問題例：
• 相対距離のリスト→絶対距離のリスト
• リスト中の数の和
• 木の高さ
知識(履歴)の損失
関数：文脈独立
• 単独，あるいは再帰中での呼び出しであっても，同じよ
うに機能する(同じ引数なら同じ結果を返す)．
• 文脈独立性は利点でもあるが，そうでない場合もある．
• 再帰的な評価の間の履歴を覚えていない．
– 時に構造的再帰関数を，複雑化，低効率化する．
– 時に生成的再帰に破滅的欠陥をもたらす．
追加引数(accumulator)により知識(履歴)を蓄積し，解決
Accumulator スタイルの関数を設計する
関数の accumulator-style 化
万能の決定的方法はないが指針はある
1. accumulator-style が有益か，必要かを認識：
• 構造的再帰の場合で，再帰の結果を再帰的な補
助関数により処理 → accumulator の導入を考慮
• 生成的再帰の場合で，履歴なしでは結果を生成
し損ねる可能性がある場合 (判断は容易でない)
2. 1の場合，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] 先頭としてリストに追加 (rest alon)に対して，
[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.相対距離リスト→絶対距離リスト
40をリストの先頭として，絶対距離のリストに変換
(rela2abs (rest alon)) できたら，その各要
素に，50を加算すれば，絶対距離のリストが完了． 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
N 1
合計
原点
50
90
160
190
220
i
1
例題1.相対距離リスト→絶対距離リスト
問題サイズNを増やすにつれ，必要時間は問題サイズNの
２乗に比例して増加：
N 1
(rela-2-abs (list 0 ... N))
例：N=100から200に増やすと時間は2倍でなく4倍．
問題の単純さの割に「仕事」の量は膨大．
i
1
改善例：相対距離のリストをたどりながら絶対距離を計算．
「知識(履歴)」の損失を防ぐ追加引数：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))
各節にデータを含まない二分木tree は下記のいずれか
1. empty (子ノードのない leaf ．再帰的なtree定義の基底)
2. 部分木を持つ節を表すnode構造体 (make-node tleft
tright)
• tleft, tright は左と右の部分木の treeデータ．
• この節と，各部分木tleft，trightの間には，枝があるとする．
empty
(make-node
(make-node
(make-node
empty empty)
empty
左の子(部分木) 右の子
(make-node
empty
概念的には
empty))
枝がある
empty)
例えばここ
が対応
例題3. 木構造の高さ
データ定義は2つの場合を持つので，それを処理する関数
も，2つの場合のcond節を持つ．節がemptyでない場合，
データ定義と同様に，自己参照(再帰呼出) height を持つ．
;; 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))))]))
部分木がある場合，abtと部分木の間にある枝の数（1）と，左右の
部分木のうち，高い方の高さを加えると，abtの高さが求まる．
例題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 ...)))
accmuは何を表すだろうか？
例題3.木構造の高さ
accum： height-a が辿ってきた枝の数を表す．
– 初期値は0 (辿った枝は0)
– 再帰的に枝を辿って，子nodeに移る ⇒ accum を 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.木構造の高さ
• accum：rootからleafへの経路上の height-a の再帰数
• 基底ケースの結果は accumの値(=高さ(枝の数))
• 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(1). ノードに値を持つ二分木
各節点から出る枝が二本以下の木構造
節の構造体定義 (define-struct node (val left right))
二分木はいずれかである（ここでは各ノードのデータ
をvalとする）
1. empty ;;ノードがない場合。再帰的なtree定義の基底
2. (make-node v tl tr) ;;値vを持つノード．ここで tl, tr は部分木
empty (make-node
63 empty empty)
(make-node
63
(make-node
29 empty
(make-node
89
empty empty))
empty)
練習2(2). ノードに値を持つ二分木
前頁の二分木について、以下を求めるプロ
グラムをアキュムレータスタイルで作成
せよ。ただし，各ノード（節や葉）がもつ値
は数値とする。
1. 根からある葉にいたる経路中の値の合計の
うち、最大のものを求める
2. 木の節、および葉に含まれる値の合計
二分木へのデータの追加
;; 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))]
emptyの場合，その
[else
ノードの値とするよう
(make-node (node-val tree)
に変更してみよう．
(node-left tree)
(add-node (node-right tree) val))])]))
経路の値の合計の最大のもの
（非アキュムレータスタイル）
;;max-path-value : node->number
(define (max-path-value a-tree)
(cond
[(empty? a-tree) 0]
[else
(max (+ (node-val a-tree)
(max-path-value (node-left a-tree)))
(+ (node-val a-tree)
(max-path-value (node-right a-tree))))
]))
経路の値の合計の最大のもの
（アキュムレータスタイル）
;;max-path-value2 : node -> number
(define (max-path-value2 a-tree)
(local ((define (max-path-accum a-tree accum)
(cond
[(empty? tree) accum]
[else
(max
(max-path-accum (node-left a-tree)
(+ accum (node-val a-tree)))
(max-path-accum (node-right a-tree)
(+ accum (node-val a-tree))))])))
(max-path-accum a-tree 0)))
木の節、および葉に含まれる値の
合計（非アキュムレータスタイル）
;;sum-node-values : node -> number
(define (sum-node-values a-tree)
(cond
[(empty? a-tree) 0]
[else
(+ (node-val a-tree)
(sum-node-values (node-left a-tree))
(sum-node-values (node-right a-tree)))]))
木の節、および葉に含まれる値の
合計（アキュムレータスタイル）
;;sum-node-values-accum : node number -> number
(define (sum-node-values2 a-tree)
(local ((define (sum-node-values-accum a-tree accum)
(cond
[(empty? a-tree) accum]
[else
(sum-node-values-accum
(node-left a-tree)
(sum-node-values-accum
(node-right a-tree)
(+ (node-val a-tree) accum)))])))
(sum-node-values-accum a-tree 0)))
課題
課題. 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