Scala 代数的データ型 超入門

代数的データ型の基本的な使い方を説明します。

この記事はわりとScalaの基本的なところを前提としていると思います。

練習の解答例は別記事に掲載します。

# 代数的データ型

以下の3つを合わせて代数的データ型と呼びます。

1. 列挙型
2. 直積型
3. 直和型

これらを1つずつ見ていきます。

# 列挙型

種類を区別するための型です。他言語の`enum`に相当します。

Enumerationを利用して書くことも出来ますし、case classを利用して代数的データ型を表現することも出来ます。列挙型については、Enumerationを利用した方法で話を進めたいと思います。

## Enumerationを使った例

```scala
object Color extends Enumeration {
  val Blue, Red, Green, White = Value
}
```

## case classを使った例

```scala
sealed trait Color
case class Blue() extends Color
case class Red() extends Color
case class Green() extends Color
case class White() extends Color
```

この例での`Color`を型（型構築子）、`Blue`などをコンストラクタ（データ構築子）と呼びます。

※ コンストラクタは構築子と訳されます。用語は括弧書きの型構築子やデータ構築子と呼ばれることが一般的です。

## idとapply

idメソッドとapplyメソッドを指定すれば数値と相互変換できるようになります。

例を示します。

```scala:enum.scala
object Color extends Enumeration {
  val Blue, Red, Green, White = Value
}

object Main {
  import Color._

  def main(args: Array[String]): Unit = {
    // id
    println(Blue.id)
    println(Red.id)
    println(Green.id)
    println(White.id)
    // apply
    println(Color(0))
    println(Color(1))
    println(Color(2))
    println(Color(3))
    // maxId
    println(Color.maxId)
    // values
    println(Color.values)
    // withName
    println(Color.withName("Red"))
  }
}
```
```text:実行結果
0
1
2
3
Blue
Red
Green
White
4
Color.ValueSet(Blue, Red, Green, White)
Red
```

例にも示しましたが、他にも色々なメソッドが使えます。こちらのページも参考にしてみてください。

[Scala列挙型メモ](http://www.ne.jp/asahi/hishidama/home/tech/scala/enumeration.html)

## Bool

真偽値を表す列挙型を表現してみましょう。

```scala:定義
object Bool extends Enumeration {
  type Bool = Value
  val True, False = Value
}
```

## 練習

【問1】光の三原色と、2つの色を混合する関数`mix`を定義してください。混ぜることによってできる色も定義の対象とします。ただし同じ成分同士は強め合わないものとします。

ヒント: `mix(a:Color.Value, a:Color.Value)`, その他の色 `Green, Cyan, Yellow, White`


# 直積型

内部に値を持つ型です。他言語の構造体に相当します。馴染みのない用語かもしれませんが、集合論に由来します。

## 例

同名の例を示します。

```scala:point.scala
sealed trait Coordinates
case class Point(x: Int, y: Int) extends Coordinates

def offset(p1: Point, p2: Point): Point = {
  Point(p1.x + p2.x, p1.y + p2.y)
}

val p1 = Point(2, 3)
val p2 = Point(1, 1)
println(offset(p1, p2))
```
```text:実行結果
Point(3,4)
```

フィールドの値はパターンマッチで取り出します。名前による方法はレコード構文として後述します。

## 直積

何が積なのかというイメージを説明します。

先ほどの例で`Point(3, 4)`というのは、`3`と`4`が組み合わさって1つのデータを構成しています。これを`3*4`のような因数の組み合わせで1つの項を構成しているように捉えます。

集合論による説明は次の記事を参照してください。

* [@CyLomw](https://twitter.com/CyLomw): [Haskell - GHC 拡張を使って直積っぽい型の表記とかしてみる - Qiita](http://qiita.com/CyLomw/items/7e72e98cfe1c8026df2a) 2015.1.13

## 練習

【問2】x,y,w,hを表現した`Rect`型を定義して、`Rect`に`Point`が含まれるかどうかを判定する関数`contains`を実装してください。

具体的には以下のコードが動くようにしてください。

```scala:rect.scala
println(contains(new Rect(2, 2, 3, 3), Point(1, 1)))
println(contains(new Rect(2, 2, 3, 3), Point(2, 2)))
println(contains(new Rect(2, 2, 3, 3), Point(3, 3)))
println(contains(new Rect(2, 2, 3, 3), Point(4, 4)))
println(contains(new Rect(2, 2, 3, 3), Point(5, 5)))
```

```text:実行結果
false
true
true
true
false
```

# 直和型

列挙型にフィールドを付加することで、複数の直積型を定義したものです。列挙型と直積型の両方の特徴を併せ持っています。

```scala:例
sealed trait Foo
case class Bar(x: Int, y: Int) extends Foo
case class Baz(x: Int, y: Int, z: Int) extends Foo
```

この名前も集合論に由来します。複数の直積型の和だと捉えれば、イメージしやすいかもしれません。

* `Bar Int Int | Baz Int Int Int` → Int*Int + Int*Int*Int

※ C言語では共用体に相当しますが、C言語のように共用体のフィールドを選ぶことで解釈を変えることはできません。区別が保持されるという意味合いでF#では判別共用体と呼びます。

## サンプル

```direct_sum.scala
sealed trait Test
case class TestInt(x: Int) extends Test
case class TestStr(x: String) extends Test

def foo(a: Test): String = a match {
  case TestInt(1)   => "bar"
  case TestStr("1") => "baz"
  case _            => "?"
}

println(foo(TestInt(0)))
println(foo(TestInt(1)))
println(foo(TestStr("0")))
println(foo(TestStr("1")))
```

```text:実行結果
?
bar
?
baz
```

関数の引数は同一の型しか受け付けないため、通常は数値`Int`と文字列`String`の両方を渡すことはできません。この例では代数的データ型を挟むことでどちらも渡せるようにしています。

## オブジェクト指向との比較

オブジェクト指向の感覚では`Test`が基底クラス、`TestInt`と`TestStr`が派生クラスに相当します。関数の扱いは基底クラスのメソッドを派生クラスでオーバーライドする感覚に近いです。

```scala:direct_sum_object.scala
abstract class Test {
  def foo: String = "?"
}

class TestInt(x: Int) extends Test {
  override def foo: String = {
    if (x == 1) {
      "bar"
    } else {
      super.foo
    }
  }
}

class TestStr(x: String) extends Test {
  override def foo: String = {
    if (x == "1") {
      "baz"
    } else {
      super.foo
    }
  }
}

println(new TestInt(0).foo)
println(new TestInt(1).foo)
println(new TestStr("0").foo)
println(new TestStr("1").foo)
```

```text:実行結果
?
bar
?
baz
```

### オーバーロード

この例ではわざわざ型を作らなくてもオーバーロードした方が簡単です。

```scala:direct_sum_overload.scala
class Test {
  def foo: String = "?"
  def foo(x: Int): String = {
    if (x == 1) {
      "bar"
    } else {
      foo
    }
  }
  def foo(x: String): String = {
    if (x == "1") {
      "baz"
    } else {
      foo
    }
  }
}

println(new Test().foo(0))
println(new Test().foo(1))
println(new Test().foo("0"))
println(new Test().foo("1"))
```

```text:実行結果
?
bar
?
baz
```

## リスト

リストは直和型として定義されています。

```scala:定義
sealed trait List[+A]
```

※ `A`は型変数と呼ばれ任意の型が入ります。今回の範囲を超えるため詳細は省略します。

### 型シノニム

文字のリストが文字列です。`List[Char]`（文字のリスト）に`MyString`という別名を付けています。

```scala:定義
type MyString = List[Char]
```

このような別名を**型シノニム**と呼びます。[synonym](http://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%8E%E3%83%8B%E3%83%A0)は**同意語・別名**という意味です。

## 練習

【問3】`Rect`と`Point`を2次元と3次元の両方に対応させて、問2の`contains`も対応させてください。

具体的には以下のコードが動くようにしてください。

```rect3d.scala
println(contains(new Rect(2, 2, 3, 3), new Point(1, 1)))
println(contains(new Rect(2, 2, 3, 3), new Point(2, 2)))
println(contains(new Rect(2, 2, 3, 3), new Point(3, 3)))
println(contains(new Rect(2, 2, 3, 3), new Point(4, 4)))
println(contains(new Rect(2, 2, 3, 3), new Point(5, 5)))
println(contains(new Rect3D(2, 2, 2, 3, 3, 3), new Point3D(1, 1, 1)))
println(contains(new Rect3D(2, 2, 2, 3, 3, 3), new Point3D(2, 2, 2)))
println(contains(new Rect3D(2, 2, 2, 3, 3, 3), new Point3D(3, 3, 3)))
println(contains(new Rect3D(2, 2, 2, 3, 3, 3), new Point3D(4, 4, 4)))
println(contains(new Rect3D(2, 2, 2, 3, 3, 3), new Point3D(5, 5, 5)))
```
```text:実行結果
false
true
true
true
false
false
true
true
true
false
```

# レコード構文

直積型や直和型のフィールドに名前を付けることができます。これを**レコード構文**と呼びます。

※Haskellのレコード構文を強引に翻訳したので、本当にScalaでこうなのかあまり自信がありません。

[Haskellのレコード構文をScalaで書きたい](http://ja.stackoverflow.com/questions/9017/haskell%E3%81%AE%E3%83%AC%E3%82%B3%E3%83%BC%E3%83%89%E6%A7%8B%E6%96%87%E3%82%92scala%E3%81%A7%E6%9B%B8%E3%81%8D%E3%81%9F%E3%81%84)

実装としては、case classを使うので、直和型、直積型とあまり変わりがありません。

```scala:例
sealed trait Data
case class Foo(bar: Int, baz: String) extends Data
```

## 生成

```scala:例
Foo(bar = 1, baz = "a")
```

無名のときと同じ方法でも生成できます。その場合でも`print`では名前が表示されます。

両方の例を示します。

```scala:record.scala
sealed trait Data
case class Foo(bar: Int, baz: String) extends Data

println(Foo(bar = 1, baz = "a"))
println(Foo(1, "a"))
```
```text:実行結果
Foo(1,a)
Foo(1,a)
```

## フィールド値の取得

フィールド名がそのままフィールド値を取得する関数になります。無名のときと同様にパターンマッチでも取り出せます。レコード構文でパターンマッチすることもできます。

```scala:record_g.scala
sealed trait Data
case class Foo(bar: Int, baz: String) extends Data

val f1 = Foo(bar = 1, baz = "a")
println(f1)
println(f1.bar, f1.baz)
val a, b = f1
println(a, b)
val c = f1.bar
println(c)
```
```text:実行結果
Foo(1,a)
(1,a)
(Foo(1,a),Foo(1,a))
1
```

## 一部を変更したコピー

Scalaの変数は値を書き換えることができませんが、フィールドも同様です。その代わり一部の値を変更したコピーを生成できます。

例を示します。

```scala:record_copy.scala
sealed trait Data
case class Foo(bar: Int, baz: String) extends Data

val f = Foo(bar = 1, baz = "a")
println(f)
// f.bar = 2 // 直接の書き換えは出来ない
val g = f.copy(bar = 2)
println(g)
```
```text:実行結果
Foo(1,a)
Foo(2,a)
```

## 練習

【問4】問2の解答をレコード構文で書き直してください。

# 参考
## 代数的データ型全般

* [代数的データ型 on Scala](http://modegramming.blogspot.jp/2012/07/30-3-on-scala.html)
* [@xuwei_k](https://twitter.com/xuwei_k) [代数的データ型とshapelessのマクロによる型クラスのインスタンスの自動導出](http://d.hatena.ne.jp/xuwei/20141207/1417940174)
* [@kmizu](https://twitter.com/kmizu) [ひょっとしたら役に立つかもしれないScala Tips(4) - パターンの漏れを検出する](http://kmizu.hatenablog.com/entry/20091229/1262091617)

## Enumerationまわり

* [ScalaのEnumerationは使うな Scalaで列挙型を定義するには ](http://xerial.org/scala-cookbook/recipes/2012/06/29/enumeration/)
* [Scala列挙型メモ](http://www.ne.jp/asahi/hishidama/home/tech/scala/enumeration.html)
* [How to deal with enumerations and path-dependent types in Scala](http://stackoverflow.com/questions/4851898/how-to-deal-with-enumerations-and-path-dependent-types-in-scala)

## 直和型まわり

* [@shinpei0213](https://twitter.com/shinpei0213) [Scala で直和型](http://nekogata.hatenablog.com/entry/2014/09/07/174814)
* [Scalaクラスメモ ケースクラス](http://www.ne.jp/asahi/hishidama/home/tech/scala/class.html#h_case_class)

## レコード構文まわり

* [Haskellのレコード構文をScalaで書きたい](http://ja.stackoverflow.com/questions/9017/haskell%E3%81%AE%E3%83%AC%E3%82%B3%E3%83%BC%E3%83%89%E6%A7%8B%E6%96%87%E3%82%92scala%E3%81%A7%E6%9B%B8%E3%81%8D%E3%81%9F%E3%81%84)
* [@xuwei_k](https://twitter.com/xuwei_k) [Scalaで抽象メソッドをoverrideする際にoverride修飾子を付けるべきかどうかの是非](http://d.hatena.ne.jp/xuwei/20131220/1387509706)
* [What's the difference between fun and fun() in Scala?](http://stackoverflow.com/questions/8228025/whats-the-difference-between-fun-and-fun-in-scala)

# ソースコード

[scala_algebra](https://github.com/shigemk2/scala_algebra)