Document

Purely Functional Data Structures 輪講
第10章
“Data-Structural Bootstrapping”
2006/07/21 いなば
[email protected]
今日の内容

Data-Structural Bootstrapping
ある抽象データ構造を作るときに、実装の中で
その抽象データ構造自身を利用すること
① Structural Decomposition


実装の中で自分自身を再帰的に使用するパターン
 (やや微妙な)例：普通のList
② Structural Abstraction

同じインターフェイスを持つ別の実装をラップして
機能を追加したり計算量を改善したりするパターン
 例: ExplicitMin Heap (Ch3):
③ Bootstrapping To Aggregate Types

型 t に関する実装を使って t list などに関する
効率的な実装を作るパターン
① Structural Decomposition

実装の中で自分自身を再帰的に使用
 Uniform
type ‘a list = Nil
| Cons of ‘a * ‘a list
 Non-uniform
type ‘a seq = Nil
| Cons of ‘a * (‘a*’a) seq
注意事項 : Non-Uniform Recursion
(Polymorphic Recursion)

このようなデータ型は、MLの型システムでは
あまりうまく扱えない
type ‘a seq = Nil
| Cons of ‘a * (‘a*’a) seq
let rec length s =
match s with Nil -> 0
| Cons(_,t) -> 1 + 2*(length t)
File "test.ml", line 7, characters 36-37:
This expression has type ('a * 'a) seq but is here used with type 'a seq
注意事項 : Non-Uniform Recursion
(Polymorphic Recursion)

方法１ : Coercion
type ‘a EP
=
|
type ‘a seq =
|

E of ‘a
P of ‘a EP * ‘a EP
Nil
Cons of EP ‘a * ‘a seq
方法２ : Explicit Type Annotation (Haskell)
len :: Seq a -> Int
len s =
case s of Nil
-> 0
Cons _ t -> 1 + 2*(len t)
例１
Binary Random-Access List

Rivisited
さっきの
type ‘a seq = Nil
| Cons of ‘a * (‘a*’a) seq
は実用上はあまり意味がない。
（サイズ2n-1のリストしか表現できない）
→ Numerical Representation の考え方で
→ “BinRan.hs”
例１
Binary Random-Access List

Rivisited
第９章の RList と何が違うのか？
type ‘a tree
=
|
type ‘a digit =
type ‘a rlist =
Leaf of ‘a
Node of ‘a tree * ‘a tree
Zero | One of ‘a tree
(‘a digit) list
 本質的な違いはない

cons, head, tail, get, set は O(log n)
 Non-Uniform
Recursion によって
桁ごとのweightが倍々になっていることを型で保証
 「次の桁」を得るのが簡単

Exercise 10.2
Zeroless表現

前回の「Zeroless 表現」も同様にnonuniform recursionで実現できる
 cons,
head, tail が amortized O(1)
type ‘a seq =
Nil
| One
of ‘a * (‘a*’a) seq
| Two
of ‘a * ‘a * (‘a*’a) seq
| Three of ‘a * ‘a * ‘a * (‘a*’a) seq
例２
Bootstrapped Queues

復習 : Banker’s Queue
type ‘a queue = int * ‘a list lazy_t
* int * ‘a list lazy_t
let rotate (fl,f,rl,r) =
(fl+rl, f @ (rev r), 0, [])

Banker’s Queue の問題点
 Append

が Left-Associative に使われる
計算量的には問題ないが、実用面では少し遅い
(((f @ (rev r1)) @ (rev r2)) @ (rev r3)) @ ..
例２
Bootstrapped Queues

どうするか？
 実際に
append はしないで、リストのリストとして
とっておく。
(((f @ (rev r1)) @ (rev r2)) @ (rev r3)) @ ..
{ (rev r1), (rev r2), (rev r3), ... }

このリスト↑に適用したい演算は？
 先頭からの取り出し
 末尾への追加
Queue !!
例２
Bootstrapped Queues

実装の概要
type ‘a queue = int * ‘a list lazy_t
* (‘a list lazy_t) queue
* int * ‘a list lazy_t
let rotate (fl,f,m,rl,r) =
(fl+rl, f, snoc m (rev r), 0, [])
let tail (fl,_::[],m,rl,r) =
(fl-1, head m, tail m, rl, r)
例２
Bootstrapped Queues

計算量
r) の suspension が作られるタイミング・
評価されるタイミングは Banker’s Queue と同じ
 (rev

rev の分に関しては、Amortized O(1)
 snoc,tail
は内部Queueの snoc,tail を呼び出す
内部 Queue の長さは O(log n)
 よって nest の深さは Hyper-logarithm O(log* n)

snoc, tail は O(log* n)
 log* (265536) = 5 なので、実質的に定数

② Structural Abstraction

同じインターフェイスを持つ別の実装をラップし
て機能を追加したり計算量を改善する
 Queueをラップして効率的にappendできるQueue
 Heapをラップして効率的にmergeできるHeap
例３
Catenable Queues

head, tail, cons, snoc, append が
Amortized O(1) な Queue
 head,

tail, cons ができるのでListとも呼べる
発想はさっきのBootstrapped Queuesと同じ
 すでに既存の
‘a queue (head, tail, snocが
amortized O(1) なもの) が実装済みと仮定
type ‘a cat = E
| C of ‘a * ‘a cat queue
→ “catQ.ml”
例３
Catenable Queues

計算量
以外は自明に O(1)
 tail も頑張って証明すると、償却 O(1)
 tail

直感的には、tail は O(Queueのサイズ) で
Queueのサイズ = それまでにappendした回数
なので append で将来の tail の分の借金を払えばOK
 Persistent
に使っても償却 O(1)にしたい時は
type ‘a cat
= E | C of ‘a * ‘a cat lazy_t queue
例４
Heaps with Efficient Merging

Heaps with Efficient Merging
merge, findMin : 最悪 O(1)
 deleteMin : 最悪 O(log n)
 insert,

実装済みと仮定する Heap
: 最悪O(1)
 mergin, findMin, deleteMin : O(log n)
 たとえば
 insert


Scheduled Binomial Heap (7.3)
Skew Binomial Heap (9.3.2)
例４
Heaps with Efficient Merging

発想はやはりさっきと同じ
→
“emheap.ml”
type ‘a emheap = E
| H of ‘a * ‘a emheap heap
 ただし、‘a
emheap間の比較演算を、
「最小要素が小さい方が小さい」と定義
② Structural Abstraction
まとめ(1)

元にするデータ構造
 どこか１カ所に関する、効率的な要素追加関数
 どこか１カ所に関する、効率的な要素取得関数
type ‘a Base
val add : ‘a -> ‘a Base -> ‘a Base
val get : ‘a Base -> ‘a
例
‘a Queue と snoc と head
 ‘a Heap と insert と findMin

② Structural Abstraction
まとめ(2)

Bootstrapされたデータ構造
type ‘a BootStrapped =
E | B of ‘a * (‘a BootStrapped) Base
 要素追加
 要素取得
let add x b =
join (Base.add x Base.empty) b
let get (B(x,_)) = x
② Structural Abstraction
まとめ(3)

Bootstrapされたデータ構造
 二つのBootstrapped構造を「結合」

Queue の append 、 Heap の merge
let join (B(x1,bs)) b =
B(x1, Base.add b bs)

Structural Abstraction によって、
このような「結合」演算を効率化できる
③ Bootstrapping To Aggregates

型 t に関する実装を使って t list などに
関する効率的な実装を作る
例
: t を key とするMapを使って、
t list を key とするMapを作る
module type Map = sig
type ‘a map; type key
val empty : ‘a map
val lookup: key -> ‘a map -> ‘a
val bind : key->‘a->‘a map->‘a map
end
例
Trie

一般的な Map
 key上の順序比較を使ったバランス木による実装


O( log(Mapのサイズ) ) 回の比較で検索
リストの比較
 要素毎の比較を辞書式順序に拡張したものとすることが
多い


最悪 O( リストの長さ ) の時間
リストをKeyとするMap
 最悪
O( Keyの長さ * log(Mapのサイズ) ) の検索時間
例
Trie

「リストをKeyとする辞書式順によるMap」
を「要素をKeyとするMap」からBootstrap
→
“trie.ml”
module Trie(B : Map) : Map =
struct
type key
= B.key list
type ‘a map = Trie of
‘a option * (‘a map) B.map
...
おはなし
Generalized Tries

Trieの考え方は、
リストに限らず一般のproductとsumによる型
に適用できる
α MapFrom_β×γ =
(α MapFrom_β) MapFrom_γ
α MapFrom_β＋γ =
(α MapFrom_β) × (α MapFrom_γ)
おはなし
Generalized Tries
type ‘a tree = E
| T of ‘a * ‘a tree * ‘a tree
module TrieOfTree(B:Map) : Map = struct
type key
= B.key tree
type ‘a map = Some ‘a * ‘a map map B.map
let
|
|
|
end
rec lookup t mp = match t, mp with
E, (None, _) -> raise Not_found
E, (Some v,_) -> v
T(e,a,b) (_,m) ->
lookup b (lookup a (B.lookup e m))

Download Report