Skip to content

Instantly share code, notes, and snippets.

@totem3

totem3/gist:30bdb75e246e07941442

Created January 7, 2015 09:25
Show Gist options
  • Save totem3/30bdb75e246e07941442 to your computer and use it in GitHub Desktop.
Save totem3/30bdb75e246e07941442 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.txt
!SLIDE
# 7章 最小高さ木の構築
!SLIDE
与えられた整数のリストが木の周縁となるような、葉にラベルがついた二分木のうち高さが最小のものを組み立てるという問題を考察する
周縁 = 葉のラベルを左から右への順で並べたリスト
!SLIDE
与えられた整数が周縁になり、高さが最小になる木を構築するには有名なアルゴリズムが２つある
* 再帰的にトップダウンで解くもの
* 反復的にボトムアップで解くもの
形は違うけどどちらも高さは最小になる
!SLIDE
# トップダウン
```hs
*Main> putStr $ drawVerticalTree $ toDataTree $top [1..10]
.
|
--------------
/ \
. .
| |
------- -------
/ \ / \
. . . .
| | | |
-- --- -- ----
/ \ / \ / \ / \
1 2 3 . 6 7 8 .
| |
-- --
/ \ / \
4 5 9 10
```
!SLIDE
# ボトムアップ
```hs
*Main> putStr $ drawVerticalTree $ toDataTree $ bottom [1..10]
.
|
--------------
/ \
. .
| |
----- --------
/ \ / \
. . . .
| | | |
-- -- -- -----
/ \ / \ / \ / \
9 10 7 8 1 2 . .
| |
-- --
/ \ / \
5 6 3 4
```
!SLIDE
# より一般的に考える
与えられたリストを葉のリストだとみなせば、最小の高さを線形時間で解く有名なアルゴリズムがある。
では、**複数の木が高さと一緒に渡された時**、そこから最小の高さの木を構築する線形時間のアルゴリズムがあるか？
※さっきのは、「複数の木」として葉のリストが渡された特殊なケースと考えることができる
!SLIDE
# Goalを確認
複数の木が高さと一緒にリストとして渡されたとき、
そこから単一の最小高さ木を構築する線形時間のアルゴリズムを導出すること
!SLIDE
# 最初の段階
入力として渡されるのは木の高さを表す整数のリスト
本当は複数の木から１つの木を構築するが、最小高さ木を考える上では高さを考えれば十分だから（多分）
!SLIDE
# 最初の段階
* 木の高さを表す自然数の列 xs = [x1,x2,x3,...,xn]
* 周縁がxsの木
* 周縁：葉のラベルを左から右への順で並べたリスト
* costが最小になるものを組み立てる
!SLIDE
# costの定義
```hs
cost (Leaf x) = x
cost (Fork u v) = 1 + (cost u `max` cost v)
```
通常の木の高さを求める関数との違いは、葉のラベルを高さとみなしている点。
(普通なら Leaf x の高さは1になるが、 Leaf x の cost は x)
!SLIDE
# 問題は以下の計算をすること
```hs
minBy cost . trees
```
* trees を与えられた周縁を持つ全ての木を組み立てる関数
* minBy cost は最小の cost の木を選択する
!SLIDE
# trees [1,2,3,4,5] はこんな感じ
```hs
. . . . . . .
| | | | | | |
+- 1 +- . +- 1 +- . +- . +- 1 +- .
| | | | | | | | | | |
`- . | +- 1 `- . | +- 1 | +- . `- . | +- 1
| | | | | | | | | | | |
+- 2 | `- 2 +- . | `- . | | +- 1 +- 2 | `- 2
| | | | | | | | | | |
`- . `- . | +- 2 | +- 2 | | `- 2 `- . `- .
| | | | | | | | | |
+- 3 +- 3 | `- 3 | `- 3 | `- 3 +- . +- .
| | | | | | | | |
`- . `- . `- . `- . `- . | +- 3 | +- 3
| | | | | | | | |
+- 4 +- 4 +- 4 +- 4 +- 4 | `- 4 | `- 4
| | | | | | |
`- 5 `- 5 `- 5 `- 5 `- 5 `- 5 `- 5
. . . . . . .
| | | | | | |
+- 1 +- . +- . +- 1 +- . +- . +- .
| | | | | | | | | | | |
`- . | +- 1 | +- . `- . | +- 1 | +- . | +- .
| | | | | | | | | | | | | | |
+- . | `- . | | +- 1 +- . | `- . | | +- 1 | | +- .
| | | | | | | | | | | | | | | | | |
| +- 2 | +- 2 | | `- 2 | +- . | +- . | | `- . | | | +- 1
| | | | | | | | | | | | | | | | | | |
| `- . | `- . | `- . | | +- 2 | | +- 2 | | +- 2 | | | `- 2
| | | | | | | | | | | | | | | | | |
| +- 3 | +- 3 | +- 3 | | `- 3 | | `- 3 | | `- 3 | | `- 3
| | | | | | | | | | | | | |
| `- 4 | `- 4 | `- 4 | `- 4 | `- 4 | `- 4 | `- 4
| | | | | | |
`- 5 `- 5 `- 5 `- 5 `- 5 `- 5 `- 5
```
!SLIDE
# もしくはこんなん
```
. . . . . . .
| | | | | | |
------- ------- ------- ------ ------- ------- ------
/ \ / \ / \ / \ / \ / \ / \
. 5 . 5 . 5 1 . . 5 . 5 1 .
| | | | | | |
----- ----- ----- ----- ----- ----- -----
/ \ / \ / \ / \ / \ / \ / \
. 4 . 4 1 . . 5 . . 1 . . 5
| | | | | | | |
---- --- ---- ---- -- -- --- ---
/ \ / \ / \ / \ / \ / \ / \ / \
. 3 1 . . 4 . 4 1 2 3 4 2 . 2 .
| | | | | |
-- -- -- -- -- --
/ \ / \ / \ / \ / \ / \
1 2 2 3 2 3 2 3 3 4 3 4
. . . . . . .
| | | | | | |
------- ------ ------ ------ ------ ------- ------
/ \ / \ / \ / \ / \ / \ / \
. . 1 . . . . . 1 . . . 1 .
| | | | | | | | | | |
-- ---- ----- ---- -- --- -- ----- -- --- -----
/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
1 2 . 5 2 . . 3 4 5 1 . 4 5 . . 1 2 3 . 2 .
| | | | | | | |
-- ---- -- -- -- -- -- ---
/ \ / \ / \ / \ / \ / \ / \ / \
3 4 . 5 1 2 2 3 2 3 4 5 4 5 3 .
| |
-- --
/ \ / \
3 4 4 5
```
!SLIDE
# trees の最初の定義
```hs
trees :: [Int] -> [Tree]
trees [x] = [Leaf x]
trees (x:xs) = concatMap (prefixes x) (trees xs)
prefixes :: Int -> Tree -> [Tree]
prefixes x t@(Leaf y) = [Fork (Leaf x) t]
prefixes x t@(Fork u v) = [Fork (Leaf x) t] ++ [Fork u' v | u' <- prefixes x u]
```
prefixes x t は、木 t の一番左の葉として x を挿入した場合の全ての木のリスト
!SLIDE
# ここから、森(Forest)や背骨(Spine)を使った定義に変形していく
まず foldrn を導入する
!SLIDE
# foldrnの話
foldr1 , foldr の型を見てみましょう
```hs
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr1 :: (a -> a -> a) -> [a] -> a
```
* 空でないリストに対して使いたいので、 foldr は論外。
* foldr1 では、１つの型しか取れない（入力のリストの要素の型と出力の要素の型が一致してないといけない）
* 今回は [Int] を取って [Tree] を返したいので、 foldr1 では足りない
* → **foldrnを定義する**
!SLIDE
# foldrn
```hs
foldrn :: (a -> b -> b) -> (a -> b) -> [a] -> b
foldrn f g [x] = g x
foldrn f g (x:xs) = f x (foldrn f g xs)
```
!SLIDE
# foldrnを使ってtreesはこう定義できる
```hs
foldrn :: (a -> b -> b) -> (a -> b) -> [a] -> b
foldrn f g [x] = g x
foldrn f g (x:xs) = f x (foldrn f g xs)
trees :: [Int] -> [TreTreee]
trees = foldrn (concatMap . prefixes) (wrap . Leaf)
wrap x = [x]
```
!SLIDE
# 木があれば森もある
次に森を導入する。森は単に木のリストのこと
```hs
type Forest = [Tree]
```
!SLIDE
# 森を使って trees を定義し直す
森のリストを組み立ててから、森を巻き上げて（rollupして）木にする
```hs
trees = map rollup . forests
forests :: [Int] -> [Forest]
forests = foldrn (concatMap . prefixes) (wrap . wrap . Leaf)
prefixes :: Int -> Forest -> [Forest]
prefixes x ts = [Leaf x : rollup (take k ts) : drop k ts | k <- [ 1 .. length ts]]
rollup :: Forest -> Tree
rollup = foldl1 Fork
```
!SLIDE
* forests が Int のリストから森のリストを作る関数
* prefixes x ts は、木 t を取ってたのが森 ts を取るようになり、森 ts の左端に葉 x を挿入した時の全ての森のリストを返す関数になった
* rollup は森を1つの木に巻き上げる関数。 森＝木のリストを Fork で畳み込んでいくだけ
!SLIDE
# 背骨
この trees ではそれぞれの森は木の**左背骨**という
!SLIDE
# 左背骨
もっとも左にある葉から根までの道筋にある右部分木の並び
(あとで出てくるので忘れないように)
!SLIDE
prefixes は、最初の定義より森を使った2番目の定義のほうが望ましい
なぜなら、最終的な気が組み立てられる様子が分かりやすいから
trees については後で
!SLIDE
# minBy cost を定義
最後に、 minBy cost :: [Tree] -> [Tree] を定義する
```hs
minBy f = foldl1 (cmp f)
cmp f u v = if f u <= f v then u else v
```
この関数は最初に見つかった最小コストの木を返すので、**非決定性のある関数**
線形全順序（⪯）を導入すれば決定性にできるけど、**そうはしない**
!SLIDE
# 定義したものの効率が悪い
今の直接的に定義された minBy cost . trees は指数オーダーの時間がかかる。
なので、ここから **融合変換** を使って式変形していく
!SLIDE
# foldrnの融合則
任意のx, yについて、
```hs
h (g x) = g' x
h (f x y) = f' x (h y)
```
が成り立つならば、任意の有限で空ではないリストxsについて
```hs
h (foldrn f g xs) = foldrn f' g' xs
```
が成り立つ.
6章で出てきたのと同じように、括弧の外にあるhを内側に分配しているような感じ
!SLIDE
# 例
```hs
h (foldrn f g [x,y,z])
= h (f x (foldrn f g [y, z]))
= h (f x (f y (foldrn f g [z])))
= h (f x (f y (g z))) -- h (f x y) = f' x (h y)ならば↓
= f' x (h (f y (g z)))) -- h (f x y) = f' x (h y)ならば↓
= f' x (f' y (h (g z)))) -- h (g x) = g' x)ならば↓
= f' x (f' y (g' z))
```
!SLIDE
しかし、今使いたい hに当たる関数 minBy cost は非決定性のある関数なので、等式でつなぐのは難しい
等しくなくても、右辺が左辺を精緻化したものであればいい
!SLIDE
# ↝を導入
そこで、 f x ↝ g x を
「 f x が出力する可能性のある値の集合は、 g x が出力する可能性のある値の空ではない集合を含む」
と定義する。
!SLIDE
# 融合変換のより弱い表明
任意のxに対して
h (g x) ↝ g' x
かつ、任意のx, y, y'に対して「 h y ↝ y' ならば h (f x y) ↝ f' x (h y 」である
という**仮定のもとで**、任意の空ではない有限のリストxsに対して以下が成り立つ
h (foldrn f g xs) ↝ foldrn f' g' xs
!SLIDE
# insert 登場
```hs
minBy cost . trees $ xs
= minBy cost (foldrn (concatMap . prefixes) (wrap . Leaf) xs)
↝ foldrn insert Leaf xs
```
ちょっとわからない
!SLIDE
minBy cost (foldrn (concatMap . prefixes) (wrap . Leaf) xs)
↝ foldrn insert Leaf xs
h = minBy cost
f = concatMap . prefixes
g = wrap . Leaf
f' = insert
g' = Leaf
!SLIDE
f' = ??? = insert
g' = h . g = (minBy cost) (wrap . Leaf) = minBy cost . wrap . Leaf = id . Leaf = Leaf
--
minBy cost . wrap は、１つの Tree を取ってそれをリストに入れて、
その結果の要素がただ１つのリストからcostが最小のものを選ぶので id と同じとみなせる。
!SLIDE
ただし、関数 insert は以下の条件を満たすように**定義できるものとする**
```hs
minBy cost ts ↝ t
=> minBy cost (concatMap (prefixes x) ts) ↝ insert x t (7.1)
```
--
tを、tsの中の最小の高さの木のうちの１つとすると、
insert x t の結果は、
木のリスト ts の各要素の木に、 x を挿入してできた木のリストの最小の高さの木の一部である
```hs
prefixes :: Int -> Tree -> [Tree] -- 最初に定義したほう
prefixes x :: Tree -> [Tree]
concatMap (prefixes x) ts :: [Tree]
```
--
runhaskell tree.hs | less
!SLIDE
更に、 insert を以下の条件を満たすようにする
```hs
minBy cost . prefixes x ↝ insert x
```
--
(書いてある通り) insert x t は prefixes x t にあるコスト最小の木を返す
(これは、これを満たすように insert を定義しますよ、という話だと思っている)
!SLIDE
insert がさきほどの条件を満たしていて、以下がなりたてば(7.1)が成り立つ
```hs
minBy cost ts ↝ t
=> minBy cost (map (insert x) ts) ↝ insert x t (7.2)
```
次でこれを証明する
!SLIDE
# 7.1の証明
```
minBy cost (concatMap (prefixes x) ts) -- (7.1の左辺)
= ☆
minBy cost (concat (map (prefixes x) ts))
= ★
minBy cost (map (minBy cost . prefixes x) ts)
↝ ※
minBy cost (map (insert x) ts) -- (7.1の右辺)
```
--
☆ concatMap = concat . map
★ minBy cost . concat = minBy cost . map (minBy cost)
リストのリストを潰して１つのリストにしてから最小を取っても、各リストの最小のものを取ったリストから最小を取っても同じということ
※ f ↝ f' => map f ↝ map f' かつ g.f ↝ g.f' -- これが成り立つかどうか
```hs
f = (minBy cost . prefixes x)
f' = (insert x)
g = minBy cost . map
```
!SLIDE
# 7.2の証明
同じ周縁を持つ任意の木u, vに対して以下が成り立てば、融合条件7.2も成り立つ
```hs
cost u <= cost v => cost (insert x u) <= cost (insert x v) -- (7.3)
```
cost が小さい木に対して同じ x を insert しても、 cost の大小は変わらない
## しかし、7.3は成り立たない
!SLIDE
# 例
```
*Main> putStr $ P.drawVerticalTree $ toDataTreeWithCost tree_u
10
|
-----
/ \
9 9
|
---
/ \
5 8
|
--
/ \
6 7
*Main> putStr $ P.drawVerticalTree $ toDataTreeWithCost tree_v
10
|
-----
/ \
8 9
|
----
/ \
7 7
|
--
/ \
5 6
```
!SLIDE
# 例
```
*Main> map cost $ prefixes' 8 tree_u
[11,11,11]
*Main> map cost $ prefixes' 8 tree_v
[11,10,11,12]
```
!SLIDE
これは成り立たないが、
```
cost u <= cost v => cost (insert x u) <= cost (insert x v) -- (7.3)
```
左背骨に沿って cost を上から下へ見ていくと
u → [10,9,5]
v → [10,8,7,6]
となり、辞書順では v のほうが小さいことが分かる
!SLIDE
よって、証明できる単調性条件は
```hs
cost' u <= cost' v => cost' (insert x u) <= cost' (insert x v) -- (7.4)
ただし、
cost' = map cost . reverse . spine
```
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment