“Purely Functional Data Structures” セミナー いなば 2006/05/12
今日の予定 Chapter 1. Introduction Chapter 2. Persistence Chapter 3. Some Familiar Data Structures in a Functional Setting
関数型データ構造とは 関数型 (functional) データ構造とは何か？ 手続き型 (imperative) データ構造との違いは？ 実装者側から見ると… 破壊的更新(destructive update)、 つまり代入(assignment)を使わない 使用者側から見ると… 永続的 (persistent) である
例1： List （黒板で説明） “append xs ys” 関数を考える “update” Functional だと、O( |xs| ) Imperative なら、自明に O(1) にできる しかし元の xs は壊れる Functional なら元のxs,ysもxs@ysもそのまま使える Persistant “update” 同様
例2： Binary Search Tree (MySet.ml)
評価戦略: Strict vs. Lazy 正格 (Strict) 評価 遅延 (Lazy) 評価 関数の引数は、呼び出し前に全て評価される 最悪計算量 遅延 (Lazy) 評価 関数の引数は、その値が実際に必要になって初めて評価される 償却(amortized)計算量 詳しくは Chapter 4 以降で
用語の定義 Abstraction Implementation Object / Version Persistent Identity 型と、型上の操作関数の集まり Abstract Data Type ML でいう、モジュールの signature Implementation ADTを実際に実現したデータ型と関数の集まり ML でいう、モジュールの structure や functor Object / Version Implementation の実際のインスタンス ML でいう、普通の value Persistent Identity Informal な “同じ”データという概念
Chapter 3 おなじみのデータ構造を関数型言語で実装 Leftist Heap Binomial Heap Red-Black Tree
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)」
Leftist Heap (MyHeap.ml) insert : O(log n) merge ; O(log n) deleteMin : O(log n) findMin : O(1)
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)
Red Black Tree Binary Search Tree のバランスを保つ技法 「赤」ノードと「黒」ノード 「赤」ノードは「赤」い子を持たない亜 全ての根から葉までのパスの「黒」の個数は等しい Prop. 高さの差はたかだか２倍 (MySet.ml)
おしまい