“Purely Functional Data Structures” セミナー

Presentation on theme: "“Purely Functional Data Structures” セミナー"— Presentation transcript:

1 “Purely Functional Data Structures” セミナー
いなば 2006/05/12

2 今日の予定 Chapter 1. Introduction Chapter 2. Persistence
Chapter 3. Some Familiar Data Structures in a Functional Setting

3 関数型データ構造とは 関数型 (functional) データ構造とは何か？ 手続き型 (imperative) データ構造との違いは？
実装者側から見ると… 破壊的更新(destructive update)、 つまり代入(assignment)を使わない 使用者側から見ると… 永続的 (persistent) である

4 例1： List （黒板で説明） “append xs ys” 関数を考える “update”
Functional だと、O( |xs| ) Imperative なら、自明に O(1) にできる しかし元の xs は壊れる Functional Persistant “update” 同様

5 例2： Binary Search Tree (MySet.ml)

6 評価戦略: Strict vs. Lazy 正格 (Strict) 評価 遅延 (Lazy) 評価 関数の引数は、呼び出し前に全て評価される
最悪計算量 遅延 (Lazy) 評価 関数の引数は、その値が実際に必要になって初めて評価される 償却(amortized)計算量 詳しくは Chapter 4 以降で

7 用語の定義 Abstraction Implementation Object / Version Persistent Identity
型と、型上の操作関数の集まり Abstract Data Type ML でいう、モジュールの signature Implementation ADTを実際に実現したデータ型と関数の集まり ML でいう、モジュールの structure や functor Object / Version Implementation の実際のインスタンス ML でいう、普通の value Persistent Identity Informal な “同じ”データという概念

8 Chapter 3 おなじみのデータ構造を関数型言語で実装 Leftist Heap Binomial Heap
Red-Black Tree

9 Leftist Heap Priority Queue Heap / 半順序木 Leftist Heap
以下の操作が(効率的に)可能な集合を表すデータ構造 最小要素の取得 最小要素の削除 新しい要素の挿入 Heap / 半順序木 二分木 親ノードの値 ≦ 子ノードの値 を満たす木 最小の要素を O(1) で取得できる Leftist Heap 左の子のrank ≧ 右の子のrank を満たすHeap rank := right spine の長さ 「要素数nのLeftist HeapのRight Spineの長さはたかだか log(n+1)」

10 Leftist Heap (MyHeap.ml) insert : O(log n) merge ; O(log n)
deleteMin : O(log n) findMin : O(1)

11 Binomial Heap Tree の List による Priority Queue の実装 自然数の「２進数表現」に類似
この手法については Chapter9 で詳しく (黒板で説明) (MyHeap.ml) insert : O(log n) merge ; O(log n) deleteMin : O(log n) findMin : O(log n) ExplicitMin findMin : O(1)

12 Red Black Tree Binary Search Tree のバランスを保つ技法 「赤」ノードと「黒」ノード
「赤」ノードは「赤」い子を持たない亜 全ての根から葉までのパスの「黒」の個数は等しい Prop. 高さの差はたかだか２倍 (MySet.ml)

13 おしまい