Chris Okasaki：純粋関数型データ構造

概要

純粋関数型言語でデータ構造をどのように設計し、実装するか。

感想

原書の題名は "Purely Functional Data Structures" 。 関数型言語でのデータ構造について焦点をあてた本はあまりなかったから、 借りてみた。

確かに、関数型言語はリストというそれだけで強力なデータ構造があるから、 少なくとも私は、他のデータ構造に関して意を払うことはなかった。しかし、 この本を読んでみて、関数型言語でデータ構造を実現するのは困難であることがわかった。

第１章　はじめに　の p.11 から引用する：

ある問題のために効率的なデータ構造が必要になったとき，C プログラマであれば、 良い教科書やハンドブックが数多くあるので、探してくるだけで済むことも多い。 残念ながら、 Standard ML や Haskell のような関数型言語のプログラマはそういう贅沢なことはできない。 こういう教科書の多くは言語非依存だと自称するが、 残念ながらそれは Henry Ford のことばを借りれば、 「プログラマは望みの言語を使うことができます。ただしそれが命令型言語である場合に限ります。」 ということである。

これからわかるとおり、関数型言語で汎用の、あるいは特定目的用のデータ構造を実現するのは、 大変だということがわかる。なお、タイトルに「純粋」ということばがあるのは、 代入という破壊的更新を避ける、ということを協調するねらいがあるものと思われる。 同じページの別の箇所から引用する。

関数型データ構造の設計と実装が命令型データ構造より難しいのはなぜだろうか。 根本的な問題が２つある。１つは、効率的なデータ構造の設計・実装という観点からいって、 関数型プログラミングが破壊的更新（つまり代入） を制限しているため圧倒的に不利だということである。 これは料理の達人から包丁を取り上げているに等しい。 破壊的更新というのは包丁と同じで、使い方を誤ると危険かもしれないが、 ちゃんと使う分には非情に効率的なのである。 命令型データ構造はしばしば代入にべったり依存しているので、 関数型プログラムでは別の解決方法を探さなければならない。

洋の東西を問わず、刃物は危険だけれど役に立つ、という比喩が成り立つようだ。

理解

p.18 にあるシグネチャと実装をファイルに打ち込んで起動させたが、 使い方がわからない。そんなとき、本書を読み進んでいる方の記事がみつかった。

「純粋関数型データ構造」を読み進めるための SML/NJ Tips (matsubara0507.github.io)

この記事を参考に使い方を知ることができた。ありがたい。くどいが、確認のためにやってみた。

- use "stack1.sml";
[opening stack1.sml]
signature STACK =
  sig
    type 'a Stack
    val empty : 'a Stack
    val isEmpty : 'a Stack -> bool
    val cons : 'a * 'a Stack -> 'a Stack
    val head : 'a Stack -> 'a
    val tail : 'a Stack -> 'a Stack
  end
structure List : STACK
structure CustomStack : STACK
val it = () : unit
- List.empty;
val it = [] : 'a List.Stack
- val s1 = List.cons (6, List.empty);
val s1 = [6] : int List.Stack
- val s1 = List.cons (2, s1);
val s1 = [2, 6] : int List.Stack
- val s1 = List.cons (1, s1);
val s1 = [1, 2, 6] : int List.Stack
- val s1 = List.cons (4, s1);
val s1 = [4, 1, 2, 6] : int List.Stack
- List.head s1;
val it = 4 : int
- List.tail s1;
val it = [1,2,6] : int List.Stack
- List.isEmpty s1;
val it = false : bool
- List.isEmpty List.empty;
val it = true : bool
- CustomStack.empty;
val it = NIL : 'a CustomStack.Stack
- val s2 = CustomStack.cons (3, CustomStack.empty);
val s2 = CONS (3,NIL) : int CustomStack.Stack
- val s2 = CustomStack.cons (6	, s2);
val s2 = CONS (6, CONS (3,CONS #)) : int CustomStack.Stack
- val s2 = CustomStack.cons (9	, s2);
val s2 = CONS (9, CONS (6, CONS #)) : int CustomStack.Stack
- val s2 = CustomStack.cons (5	, s2);
val s2 = CONS (5, CONS (9, CONS #)) : int CustomStack.Stack
- CustomStack.head s2;
val it = 5 : int
- CustomStack.tail s2;
val it = CONS (9,CONS (6,CONS #)) : int CustomStack.Stack

ここで、# はなんだろう。と思ったら、先に挙げた SML/NJ Tips に書いてあるのがわかった。 再帰的なデータ構造を表示するとき、ある以上の深さは # で省略される、ということだった。

書誌情報

まりんきょ学問所 ＞ コンピュータの本 ＞ LISP, Prolog ＞ Chris Okasaki：純粋関数型データ構造