Document

“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” 関数を考える


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) 評価



関数の引数は、その値が実際に必要になって初めて
評価される
償却(amortized)計算量
詳しくは Chapter 4 以降で
用語の定義

Abstraction




Implementation



ADTを実際に実現したデータ型と関数の集まり
ML でいう、モジュールの structure や functor
Object / Version



型と、型上の操作関数の集まり
Abstract Data Type
ML でいう、モジュールの signature
Implementation の実際のインスタンス
ML でいう、普通の value
Persistent Identity

Informal な “同じ”データという概念
Chapter 3

おなじみのデータ構造を関数型言語で実装



Leftist Heap
Binomial Heap
Red-Black Tree
Leftist Heap

Priority Queue
 以下の操作が(効率的に)可能な集合を表すデータ構造




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)
おしまい

Download Report