何で走っているのだろう: Scalaでの代数的データ型のしくみと使い方

2018/04/14

Scalaでの代数的データ型のしくみと使い方

代数的データ型(Algebraic data type)
パターンマッチ

Listに対するパターンマッチ
Optionに対するパターンマッチ
代数的データ型に対するパターンマッチ
パターンマッチに条件を追加
代数的データ型とパターンマッチ

Scalaについて勉強した時のメモ(その2)です。代数的データ型の扱い方について。

※ 元々はmarkdownで書いていたテキストの転載。

代数的データ型(Algebraic data type)

端的に言うと、以下のようなデータ定義の仕方。

sealed trait Alphabet
case object Alpha extends Alphabet
case class Beta(name: String) extends Alphabet
case class Gamma(name: String, n: Int) extends Alphabet

引数の戻り値型や処理結果のパターンや、Seq型で表現できないようなリスト構造、木構造、その他必要に応じてポリモーフィックに変化するデータ型を表す際に使用する。
ざっくり説明すると、代数的データ型とは、直積型による構造体と、コンストラクタと直和型によるポリモーフィズムを表した型。
- Scala風に言うと、複数のcase objectとcase classを単一のtraitでまとめたもの。
- 全てを使う必要はない。必要に応じて必要なオブジェクトを使う。
代数的データ型は、コンストラクタと、直積型、直和型から構成される。
- 代数的("Algebraic")という単語は、直和型と直積型に由来している。 Algebraic data type - HaskellWiki
代数的データ型を返す関数の型は継承元のtraitで、条件に応じて、様々なtraitの型のインスタンスを返す。

def func(n: Int): Alphabet =
  if (n < 10) Alpha
  else if (n < 30) Beta("aaa")
  else Gamma("bbb", n)

以下のようにパターンマッチで各データパターンごとに分解できる。

xxx.func(x) match {
  case Alpha => 〜 ...
  case Beta(name) => 〜 (この中では変数nameが使える) ...
  case Gamma(name, n) => 〜 ...
}

普段よく使っている代数的データ型の一つがOption型
- scala/src/library/scala/Option.scala

sealed abstract class Option[+A] extends Product with Serializable
case object None extends Option[Nothing]
final case class Some[+A](value: A) extends Option[A]

割と他の関数型言語だと定番の書き方。
- 参考: 代数的データ型とパターンマッチによる言語比較
- (余談)代数的データ型を一般化したGADT(Generalized Algebraic Data Type)というのもある。
関数型プログラミングだと実装とデータ型を分離する傾向がある。(要出典)
- 分離されたデータ型が代数的データ型。
- データ型(クラス)に実装が付随しているオブジェクト指向とは異なる。
代数的データ型は、再帰的(帰納的)に定義される有限のデータ構造(Streamなど無限のデータ構造というのもある)
- 参照: 具象不変コレクションクラス | Scala Documentation
(余談)一応、case classには、finalを付けた方がいい: Should I use the final modifier when declaring case classes? - StackOverFlow

パターンマッチ

Scalaのパターンマッチ - Qiita
Scalaでは、リテラル(定数)、正規表現、構造(タプル、case objectやcase classなど)、代数的データ型に関するマッチなどが可能。
データ型のインスタンス(ListやTuple、Case classなど)を構造的に分解して変数に代入できる。
- オブジェクトにunapplyが定義されていれば、パターンマッチが可能。
- パターンマッチをもっと便利に-extractor(抽出子)による拡張
if-else式とは違い、データ型に対する網羅的にパターンマッチを行う。網羅的でない場合は警告がでる。(但し、エラーにはならない。) パターン漏れが防げるので積極的に活用していきたい。
データ型に対する分岐か、それ以外かでif-elseとの使い分けができる。

Listに対するパターンマッチ

次のコードはパターンマッチで書き換えた方が、ロジックがシンプルになる。

if (ls.isEmpty) 1 else ls.head

は、リストlsについてのパターンマッチ、

ls match {
  case Nil => 1
  case x::xs => x
}

と書き直せる。else節でls.headを使う時に、lsを手前の条件節でチェックしているかどうかを考慮する必要が無くなる。

ただし上記の場合は、headOptionとgetOrElseで書くのが一般的のよう。

ls.headOption.getOrElse(1)

Optionに対するパターンマッチ

次のようなケースも、リスト同様に書き直せる。

if (x.isEmpty) "hogehoge" else x.get.toString

存在するSome/Noneパターンを列挙する。

x match {
  case Some(x) => x.toString
  case None => "hogehoge"
}

Either(Right/Left)やTry(Success/Failure)の場合も同様にして、分解できる。

代数的データ型に対するパターンマッチ

以下のような代数的データ型に対するパターンマッチ。

sealed trait Alphabet
case object Alpha extends Alphabet
case class Beta(name: String) extends Alphabet
case class Gamma(name: String, n: Int) extends Alphabet

次のように書く。書き方はOption等と同じ。

x match {
  case Alpha => "A"
  case Beta(name) => "B(" + name + ")"
  case Gamma(name, n) => "C(" + name + ")"
}

パターンマッチに条件を追加

パターンマッチの場合、構造のチェックと同時に、データ型から値の取り出し、変数への束縛まで行う。
ただし、以下のような書き方をした場合、パターンマッチの本来の意味はなくなる(ただのif-else式と基本的に同じ意味しかなくなる)。

x match {
 case _ if x.isEmpty => "hogehoge"
 case _ => x.get.toString
}

パターンマッチでのifによる条件追加は以下のようなケースだと有効。パターンマッチの基本的な機能である構造的な変数の束縛、パターンの列挙(とそのチェック)の両方を使用しているため。

x match {
 case Some(x) if x == "a" => "hogehoge"
 case Some(x) => "fugafuga"
 case None => "piyopiyo"
}

1caseに複数パターンのマッチも可能。

n match {
  case 1 | 2 | 3 => "hogehoge"
  case _ => "hoge"

代数的データ型とパターンマッチ

Javaのポリモーフィズムでは、処理が各クラスごと分散してしまうというデメリットがある。
代数的データ型とパターンマッチでは、データ型はデータ型ごとに定義し、ポリモーフィックな処理はパターンマッチで一箇所に記述させる。

Compositeパターン - Wikipedia から引用してきた例(長かったのでコードの一部を改変している)。

interface FileInterface {
	public void ls(int depth);
	public boolean add(FileInterface c);
}
class File implements FileInterface {
	private String name;
	public File(String name) { this.name = name; }
	public void ls(int depth) {
		System.out.println("depth(" + depth + ") file:" + this.name);
	}
	public boolean add(FileInterface c) { return false; }
}
class Folder implements FileInterface {
	private String name;
	private List<FileInterface> fileList = new ArrayList<FileInterface>();
	public Folder(String name) { this.name = name; }
	public void ls(int depth) {
		System.out.println("depth(" + depth + ") folder:" + name);
		for (FileInterface file : fileList) { file.ls(depth + 1); }
	}
	public boolean add(FileInterface c) { return this.fileList.add(c); }
}

上記は代数的データ型とパターンマッチで書き直せる。代数的データ型は以下のように定義できる。

sealed trait FileInterface
case class File(name: String) extends FileInterface
case class Folder(name: String, f: scala.collection.mutable.ListBuffer[FileInterface]) extends FileInterface

次のようにデータを作る。

scala> val prj = Folder("crud-prj", ListBuffer(File("README.md"), File("build.sbt"), Folder("src", ListBuffer(File("Helloworld.scala"), File("XXXDao.scala"), File("ExampleController.scala")))))

ディレクトリ階層を表示する関数。

def ls(files: FileInterface, depth: Int): Unit = files match {
  case File(name) => println("depth(" + depth + ") file:" + name)
  case Folder(name, children) => {
    println("depth(" + depth + ") folder:" + name)
    children.foreach{ child => ls(child, depth + 1) }
  }
}

ディレクトリに要素を追加する関数。

def add(files: FileInterface, element: FileInterface): Boolean = files match {
  case File(name) => false
  case Folder(name, children) => { children += element; true }
}

Javaと同様の関数を書くならば、上記の書き方で問題ない。ところで、上記の関数は木構造をmutableに変更してしまう。一般に関数型プログラミングは副作用(データの破壊的な変更)を回避するため、その点において、上記の書き方は問題がある。そこで、immutableなadd関数を容易する必要がある。 immutableな関数を容易し、rootから書き換える。例えば、次のような関数が考えられる。

def addI(files: FileInterface, elem: FileInterface, path: Seq[String]): FileInterface = (files, path) match {
  case (Folder(name, children), Nil) =>
    Folder(name, children :+ elem)
  case (Folder(name, children), x::xs) =>
    Folder(name, children.map {
        case f @ Folder(name, c) if name == x => addI(f, elem, xs)
        case a => a
    } )
  case _ => throw new RuntimeException("ファイルに要素を追加しようとしたのでエラー。")
}

同様にcase classもimmutableにする

sealed trait FileInterface
case class File(name: String) extends FileInterface
case class Folder(name: String, f: Seq[FileInterface]) extends FileInterface

この関数をrootに対して適用する。次のようなコード。

val root =
Folder("project", Seq(Folder("app", Seq(Folder("controller", Seq(File("HomeController.scala"),
                                                                 File("ContentController.scala"))),
                                        Folder("view",       Seq(File("hello.scala.html"))))),
                      File("README.md")))

次のように実行する。

scala> addI(root, File("AnotherController.scala"), Seq("app", "controller"))
res24: FileInterface =
Folder(project, List(Folder(app, List(Folder(controller,List(File(HomeController.scala),
                                                             File(ContentController.scala),
                                                             File(AnotherController.scala))),
                                      Folder(view, List(File(hello.scala.html))))),
                     File(README.md)))

(注意):ただし、よりScalaらしく実装するなら、 File/Folderのようなデータ構造は、Traversableトレイトの具象クラスとして実装するほうが多分正解。
- Traversable トレイト | Scala Documentation

Scala 代数的データ型

« Scalaでの関数のしくみと使い方 Scalaでの例外系の処理のしくみと使い方 »