Scala の抽象データ型構築レシピ：Rainy Day Codings：So-net blog

	ブログをはじめるログイン

EOPL 第3章の Exercise 3..｜Scala の抽象データ型構築レシピ v.. ブログトップ

Scala の抽象データ型構築レシピ　[Scala] [編集]

Scala による抽象データ型定義の手順を誰でも追えるようなレシピ形式にするというのを考えていた。
まだこなれていないけど以下のようなもの。今のところ immutable なデータのことしか考えていない。

* Scala における抽象データ型構築レシピ

1. データ型のインターフェイスを決める。

2. 1で決めたインターフェイスの要素を以下の3種類に分類する

a. 当該データ型の値から何らかの情報を抽出するもの。
b. 当該データ型の値を元にして同じデータ型に属する新たな値を生成するもの。
c. 無から当該データ型の値を生み出すもの。定数。

3. 2で分類した a と b をメソッドとする abstract class を定義する。コンテナのように任意のデータ型に対して適用されるものの場合は型変数を付与する。以降この型変数を T とする。

4. 2で分類した c にあたるものを 3 のクラスを継承したクラスとして定義する。ここでデータ型が型変数を含まないならばこれをクラスではなく object としてよい。

5. 非定数について 3 のクラスを継承して実装を与える。

ここから以降は variance annotation を付ける作業。型変数がある場合のみ行える。

6. これまでに定義したクラスの型変数を T から +T に変える。

7. 2 で b に分類したメソッドについて以下を行う。

a. T よりも上位（クラス階層図での上）の型 U を考えてメソッドに [U >: T] という型変数を付ける。
b. 引数の T を U に変える
c. 戻り値の T を U に変える

8. 2 で c に分類した定数に対応するクラスを obect に変える。ここで継承元のクラスの型変数は Nothing にする。

* ケーススタディ1: 非負の整数

ケーススタディとしてまず非負の整数を表現するデータ型 Num を考える。

1. Num のインターフェイスは以下4つから構成される。

isZero: 値がゼロか否かを判定する
succ: 値に1を加えた値を返す
pred: 値から1を引いた値を返す
Zero: ゼロを返す

2. 上記の4つの要素は以下のように分類される

isZero: a. 当該データ型の値から何らかの情報を抽出するもの。
succ: b. 当該データ型の値を元にして同じデータ型に属する新たな値を生成するもの。
pred: b. 当該データ型の値を元にして同じデータ型に属する新たな値を生成するもの。
Zero: c. 無から当該データ型の値を生み出すもの。定数。

3. 上記の a と b をメソッドとする abstract class を定義する。

abstract class Num {
  def isZero: Boolean
  def succ: Num
  def pred: Num
}

4. c に分類した Zero を上記のクラスを継承して定義する。Num は型変数を含まないので object とする。

object Zero extends Num {
  def isZero = true
  def succ = ...
  def pred = error("Zero.pred")
}

succ メソッドは非ゼロの値を生み出すがここではまだ実装を与えられない。

5. Num を継承して非定数（つまり非ゼロ）のクラスを実装する。

class NonZero(n: Int) extends Num {
  def isZero = false
  def succ = new NonZero(n + 1)
  def pred = if (n == 1) Zero else new NonZero(n - 1)
}

非ゼロの定義ができたので Zero の未実装だった succ メソッドを埋めることができる。

object Zero extends Num {
  def isZero = true
  def succ = new NonZero(1)
  def pred = error("Zero.pred")
}

Num は型変数を含まないので手順はここで終わり。最終形は以下のとおり。

abstract class Num {
  def isZero: Boolean
  def succ: Num
  def pred: Num
}

object Zero extends Num {
  def isZero = true
  def succ = new NonZero(1)
  def pred = error("Zero.pred")
}

class NonZero(n: Int) extends Num {
  def isZero = false
  def succ = new NonZero(n + 1)
  def pred = if (n == 1) Zero else new NonZero(n - 1)
}

このレシピは具体的な実装の方法については何も述べていない。
例えばメモリの許す限り大きい整数を表現できるような実装を与えたい場合、手順の 4 までは同一で 5 の段階で実装の差が現れる。

abstract class Num {
  def isZero: Boolean
  def succ: Num
  def pred: Num
}

object Zero extends Num {
  def isZero = true
  def succ = new NonZero(1, Zero)
  def pred = error("Zero.pred")
}

class NonZero(lsd: Int, rest: Num) extends Num {
  def isZero = false
  def succ = if (lsd < 9) new NonZero(lsd + 1, rest)
             else new NonZero(0, rest.succ)
  def pred = if (lsd == 1 && rest == Zero) Zero
             else if (lsd == 0) new NonZero(9, rest.pred)
             else new NonZero(lsd - 1, rest)
}

* ケーススタディ2: スタック

次に型変数が現れる例としてスタックを考える。これは最終的には Scala By Example に書いてあるのとほぼ同じ実装になります。

1. Num のインターフェイスは以下の5つから構成される。

isEmpty: スタックが空かどうかを判定する
top: スタックの一番上の要素を返す
pop: スタックの一番上の要素を取り除いた結果のスタックを返す
push: スタックに要素を追加して結果のスタックを返す
EmptyStack: 空のスタックを返す

2. 上記の5つの要素は以下のように分類される

isEmpty: a. 当該データ型の値から何らかの情報を抽出するもの。
top: a. 当該データ型の値から何らかの情報を抽出するもの。
pop: a. 当該データ型の値から何らかの情報を抽出するもの。
push: b. 当該データ型の値を元にして同じデータ型に属する新たな値を生成するもの。
EmptyStack: c. 無から当該データ型の値を生み出すもの。定数。

ここで pop が b でなく a だというのは自明ではない。pop と push はともにスタックを返すからだ。あとで 6 以降を行うときに少なくとも両者を区別するのが良いことが分かるのだが、この時点での基準としては不十分で、これはこのレシピがまだ洗練されていないということを意味する。

しかし次の 3 を行うにあたっては a と b の区別は重要ではないのでとりあえず先に進む。

3. 上記の a と b をメソッドとする abstract class を定義する。
ここでスタックは任意のデータ型について適用されるものなので型変数 T を導入する。

abstract class Stack[T] {
  def isEmpty: Boolean
  def top: T
  def pop: Stack[T]
  def push(elem: T): Stack[T]
}

4. c に分類した EmptyStack を上記のクラスを継承して定義する。

case class EmptyStack[T] extends Stack[T] {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
  def push(elem: T) = ...
}

push の実装は例によってまだ埋められない。

なおここでは case class にしてみたけど case class にするかどうかはお好みでよいと思う。私は何かと便利なのでつい case class にするのが好きなのですが。

5. Stack[T] を継承して空でないスタックのクラスを実装する。

case class NonEmptyStack[T](head: T, rest: Stack[T]) extends Stack[T] {
  def isEmpty = false
  def top = head
  def pop = rest
  def push(elem: T) = NonEmptyStack(elem, this)
}

ここで NonEmptyStack の push を埋めることができる。

case class EmptyStack[T] extends Stack[T] {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
  def push(elem: T) = NonEmptyStack(elem, this)
}

push メソッドが NonEmptyStack と EmptyStack で変わらないことに注目して実装を Stack の方に移してもよいかもしれません。

ここまででやめてもよいけど 6 以降を実行すると Stack[Int] に Double を push すると自動的に全体が Stack[AnyVal] になるといったような柔軟な型付けをしてくれるようになる。

6. これまでに定義したクラスの型変数を T から +T に変える。

abstract class Stack[+T] { ... }
case class NonEmptyStack[+T](head: T, rest: Stack[T]) extends Stack[T] { ... }
case class EmptyStack[+T] extends Stack[T] { ... }

7. 2 で b に分類した push メソッドについて以下を行う。

するとこうなります。

abstract class Stack[+T] {
  def isEmpty: Boolean
  def top: T
  def pop: Stack[T]
  def push[U >: T](elem: U): Stack[U] = NonEmptyStack(elem, this)
}
case class EmptyStack[+T] extends Stack[T] {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
}
case class NonEmptyStack[+T](head: T, rest: Stack[T]) extends Stack[T] {
  def isEmpty = false
  def top = head
  def pop = rest
}

8. 2 で c に分類したを EmptyStack を obect に変える。ここで継承元の Stack の型変数を Nothing にする。これで最終形は以下のようになります。

abstract class Stack[+T] {
  def isEmpty: Boolean
  def top: T
  def pop: Stack[T]
  def push[U >: T](elem: U): Stack[U] = NonEmptyStack(elem, this)
}

case object EmptyStack extends Stack[Nothing] {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
}

case class NonEmptyStack[+T](head: T, rest: Stack[T]) extends Stack[T] {
  def isEmpty = false
  def top = head
  def pop = rest
}

* レシピに対する考察

今2つほど問題があると思う。

一つは途中でも述べたように a と b の区別が必ずしも直感的に自明でない場面があり、かつ明確なクライテリアとして提示できていない。

もう一つは[1] の記事のコメント欄でみずしまさんに教えてもらったりした件なのだが、immutable で generic なデータ型だとしても 6 以降に進めない場合がある。この一般的な判断基準を述べることが出来ていない。

[1] http://blog.so-net.ne.jp/rainyday/2007-08-08

2007-09-04 01:26 nice!(0) コメント(0) トラックバック(0)
共通テーマ：パソコン・インターネット