これは、ドワンゴ Advent Calendar の 7日目です。
6日目は DartのASTを触ってみる でした。
さて、会社でアドベントカレンダーやる、と言われて、なんとなく参加登録したはいいものの、特に書くこと決めてませんでした。
最近、msgpackのScalaのライブラリ作ってるので、それ完成したらそのこと書こうかな―、と思ってましたが、msgpack-javaのバグや、古いversionと新しいversionの違いと戦ってたりしたら、なかなか完成しないので別のこと書くことにしました。
というわけで、標題の
「代数的データ型とshapelessのマクロによる型クラスのインスタンスの自動導出」
という話をします。ドワンゴアドベントカレンダーだからといて、べつに変わったことはなく、いつものようなScalaネタです。
さてみなさん「代数的データ型」って知ってますか？Scalaよりもっとちゃんとした関数型言語*1では、大抵専用の構文があるので、自然と使うと思います。
OCamlでは"ヴァリアント型"といったりするやつでしょうか？
Haskellだったら、dataというキーワードで定義するやつですね。
英語だと"Algebraic data type"というらしいです。
さて、今回は "代数的データ型" 自体を詳細に解説するのが今回の目的ではありません。しかし "代数的データ型" がどんなものか？、そしてScalaにおいて、代数的データ型はどのように表現されるのか？などを知っておいてもらわないと、話が進まないので、最初は、代数的データ型自体の話をします。
さて、ありがちですが、Treeを例にして、Haskellと比較してみましょう。
Haskellだったら、例えば以下のような構文で2分木のデータを定義できますね？
data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show, Eq)
これをScalaで書くと、以下のようになります。
sealed abstract class Tree[A] final case class Leaf[A](value: A) extends Tree[A] final case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
Scala面倒ですね。しかし、代数的データ型自体の定義の面倒さはありますが、今回話すのはそこではなく「型クラスのインスタンスの自動導出」の話です。Haskellでは
deriving (Show, Eq)
と書くだけで、自動でShorやEqの型クラスのインスタンスが手に入ります。しかし、Scalaの場合には、今定義したTreeに対して、(Scalazの)EqualやShowのインスタンスは、普通の方法では自動導出は不可能です。
ここで、shapelessの具体的な説明に・・・いくのではなく、まだもう少し代数的データ型の話が続きます。
自分も詳細な理論的な説明はできませんが*2、代数的データ型の大きな特徴としては、まず以下の2点でしょうか
- 直積型
- 直和型
さきほどのTreeの例では、直和も直積も両方使ってますね。Branchが "left: Tree[A]" と "right: Tree[A]" という2つの部分から成り立ってる、というのが "直積" であり、 "TreeがLeafもしくはBranchのどちらか" ということを表現してるのが "直和" です。
代数的データ型は、とてもシンプルに考えると、その2つの特徴を持ってるだけのとても単純なものですが、とても強力で便利なものです。
普通のScalaプログラマで、代数的データ型という言葉を聞いたことがなかったという人や、なんとなくsealedを使っていた人は、"代数的データ型" というのを意識してデータ型を設計するのは、関数型なプログラマへのステップアップのためにはかなり重要だと思うので、意識するようにするといいと思います。
さて、話がそれ気味ですが、まだ少しだけ代数的データ型の話をしましょう。直和と直積、という言葉を出しましたが、それ以外にも重要な点としては、"型パラメータを取れる" こと、 "再帰的にできる" あたりでしょうか。上記のTreeの例では、既にその特徴を両方使ってますね。
再帰的な例で有名なものといえば、たとえばJsonのデータ構造などは、どのScalaのJsonのライブラリでも、sealed traitかsealed abstract classを定義して、代数的データ型として定義してると思います。
さて、ここまで
- 直積
- 直和
- 型パラメータをとれる
- 再帰的
などのキーワードを使って、代数的データ型自体の話をしました。これらの特徴が、型クラス自体や、型クラスのインスタンスの自動導出に深く関わってくるので話をしたわけです。
さて、EqualやShowくらいなら、Scalaのcase classは、自動でいい感じにやってくれますが、その他(たとえば、OrderとかMonoidとか)は、勝手にいい感じにやってくれませんね？そもそもScala標準ライブラリに直接対応する型クラスがなかったりもしますし。
勝手に、とは、OrderやMonoidの例でいうと、case class定義しただけで、それらが比較可能になるとか、足し算可能になるという意味ですが、それは普通は不可能です。
また、Equalなどの場合でも、勝手にequalsメソッドがoverrideされるとはいえ、scalaz.Equalのインスタンスが定義されることは、型安全などの、様々なメリットがあります。
*3
型クラスはとても便利なので、代数的データ型が存在したら、それらの型クラスのインスタンスを作りたいという要求は、頻繁に発生することです。
今まで説明したように、代数的データ型は、"直積" "直和" などの、シンプルないくつかの規則から成り立っているので、それらのインスタンス定義は慣れてない人にとっては難しく感じるかもしれませんが、実は大抵は単純作業です。
たとえば、以下のようなPointIntやPointという、2次元の座標を表現するクラスがあったとしましょう
final case class PointInt(x: Int, y: Int) final case class Point[A](x: A, y: A)
さて、PointIntクラスでもPointクラスでも、それらのEqualのインスタンスを定義する場合「xとyが両方とも同じだったら、全体も等価」という定義にしますね？Pointがもし3次元で、x, y, zと3つ値を持っていても同じようになるでしょう。
また、PointIntではなく、Pointのように型パラメータを持つ場合は、まずPointのEqualの定義をするためには、Aの型自体のEqualを要求しますね。
具体的な定義は以下です
implicit val pointIntEqual: Equal[PointInt] = Equal.equal{ case (PointInt(x1, y1), PointInt(x2, y2)) => x1 == x2 && y1 == y2 } implicit def pointEqual[A](implicit A: Equal[A]): Equal[Point[A]] = Equal.equal{ case (Point(x1, y1), Point(x2, y2)) => A.equal(x1, x2) && A.equal(y1, y2) }
何が言いたいかというと、Equalだったら「すべての要素が同じだったら全体も同じ」という、大抵は単純な法則によって、Equalのインスタンスを作りますし、ほかにも
- Orderだったら要素を順番に比較していく
- Monoidならそれぞれの要素を足し合わせる
- ScalacheckのArbitraryだったら、それぞれのランダムな値を作って、全体のランダムな値を作る
など、一見複雑に見えるものだとしても、代数的データ型として直積や直和の組み合わせで表現できるものなら、それぞれの型クラスのインスタンスは、実はかなりシンプルな法則のみで作れます。
なので、その「型クラス毎のインスタンス生成時の法則」のみを何らかの形で表現しておいたら、あとは自動でやってくれる仕組みが欲しくなりませんか？なりますね？
特殊な場合だけ手作業でインスタンス定義を書いて、デフォルトの定義(たとえばEqualだったらすべての要素が同じ)でいい場合は、勝手に定義して欲しくなるはずです。
はい、ここでやっとshapelessの話になります。
なぜここまで、色々と代数的データ型の話をしたのか？というと、shapelessの自動導出には、以下のような素晴らしい特徴があるからです
- 「型クラスを導出するたの型クラス」というメタ的な概念があり、それを定義できるものならば、どんな型クラスのインスタンスであっても自動導出が可能
- 基本的に、代数的データ型の定義側は、なにか特殊な決まりは必要なく、普通に定義すればいい。そして、 直和、直積、型パラメータ、再帰的なデータ型、といった、今まで説明したすべてのパターンに対応している*4
という点です。今言った、上記二点のすごさを理解してもらうのが、今回の大きな目的なのですが、ここまででどのくらいの人がついてきてるでしょうか？
上記に書いた、2つの点がとても汎用的ですごいというのは、たとえばPlayのJsonのマクロなどとくらべてみればわかりやすいと思います。
playのJsonにも、マクロでシリアライズやデシリアライズの型クラスのインスタンスを生成してくれるマクロがあります。
細かいことを考えれば、playが独自にマクロを定義していること自体は、メリットがないわではないです。しかし、ああいうパターンのものは、大抵はshapelessの仕組みを使って可能な範囲です。しかも、playのものは*5マクロの実装がまずくて、いくつか微妙な制限があったりしました。現状のplay2.3でも、型パラメータは扱えないなどの制限があり、そのあたりはshapelessの仕組みと比べて劣っています。
さて、ここからは、そのshapelessを使った具体的な自動導出の仕組みの使い方の説明・・・ではなく、
「どうやって自動導出を可能にしているのか？」
の内部実装の話をします。
もちろん、内部実装はマクロを使っています。説明したいのはそこではなく
「任意の代数的データ型について、どうやって型クラス毎の規則を定義するか？」
という話です。"任意の代数的データ型" とは、つまりcase classのそれぞれのフィールドがいくつあるかわからないし、sealed traitやsealed abstract classのサブクラスが、いくつあるかもわかりません。
「フィールドが2つの場合の定義」「フィールドのが3つの場合の定義」と個別に書かないといけないとしたら、面倒でやってられないですね？
「直積」という概念と「直和」という概念を、もっと抽象化してまとめて扱う必要があります。
そこででてくるのが、HListとCoproductです！
https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/coproduct.scala
https://github.com/milessabin/shapeless/blob/shapeless-2.0.0/core/src/main/scala/shapeless/hlists.scala
HListは、HNilも含めれば「0以上の直積を表現」するまさにそのものです。
また、(shapelessの)Coproductは、同様に直和を表現するものです。
それぞれ実際の(メソッドを除いた)定義部分はわりと短いので、そのまま引用しておきますね。
sealed trait HList final case class ::[+H, +T <: HList](head : H, tail : T) extends HList { override def toString = head+" :: "+tail.toString } sealed trait HNil extends HList { def ::[H](h : H) = shapeless.::(h, this) override def toString = "HNil" }
sealed trait Coproduct sealed trait :+:[+H, +T <: Coproduct] extends Coproduct final case class Inl[+H, +T <: Coproduct](head : H) extends :+:[H, T] { override def toString = head.toString } final case class Inr[+H, +T <: Coproduct](tail : T) extends :+:[H, T] { override def toString = tail.toString } sealed trait CNil extends Coproduct
直和や直積をCoproductやHListとして再帰的に抽象的に表現することで「フィールドが2つの場合の定義」「フィールドのが3つの場合の定義」などと書く必要がなくなります。
実際のshapelessにおける "TypeClassという名前の型クラス" では、以下のような定義になっています
def product[H, T <: HList](CHead: C[H], CTail: C[T]): C[H :: T] def coproduct[L, R <: Coproduct](CL: => C[L], CR: => C[R]): C[L :+: R]
上記の、productメソッドやcoproductメソッドなどのHListやCoproductを引数にとるメソッドさえ定義すれば、任意の代数的データ型に対応できる、という仕組みになっています。
この定義だけをみても、これでなぜすべての代数的データ型に対応できるのかはすぐには理解できないかもしれません。あとは、以下にある実際のScalazやScalacheckの型クラスの例
https://github.com/typelevel/shapeless-contrib/blob/v0.3/scalaz/main/scala/typeclass.scala
https://github.com/typelevel/shapeless-contrib/blob/v0.3/scalacheck/main/scala/package.scala
を見てみるといいと思います。現状では、Scalazでは、以下の型クラスのインスタンスが自動導出できます
- Semigroup
- Monoid
- Equal
- Order
- Show
さて、このあたりの話は、実は英語なら1年以上前にここ
http://typelevel.org/blog/2013/06/24/deriving-instances-1.html
に記事があるので読むといいと思います。
また、shapeless 2.0.0 の前提で書いたし、リンクも 2.0.0 のリンクを貼りましたが、次の shapeless の version では、(もちろん同じ機能は提供されるらしいですが) 少しこのあたりが変わるらしいので、注意してください。
あと、shapeless自体については、以前勉強会で発表したので、こちらもどうぞ
http://d.hatena.ne.jp/xuwei/20141025/1414219304
そして、このshapelessの機能使って、msgpackのシリアライズ、デシリアライズの型クラスのインスタンスの自動生成もできたので、そのうち公開したい・・・。公開しました https://github.com/msgpack4z/msgpack4z-shapeless
以上、いつも通り？少し難しめのScalaな話でしたが、ドワンゴアドベントカレンダー7日目でした。
次の8日目は Oculus Game Jam in Japan 2014 に参加してきた です
