Scalaでの再帰的implicitとRank2Type

scalaz scala

「再帰的implicit」という、普通にScala書いていたら遭遇しない話をします。なので、多くの人にとっては役に立たないだろうから、そういうのに興味のない人は読まないほうがいいです。


さて、これはekmett/freeの中にあるCofreeのEqのインスタンス(珈琲じゃなくて、Freeモナドの双対のCo Freeだよ！)
*1
をScalaに翻訳していたとき(そしてScalazに入れようとした)に遭遇した話です。以下は翻訳元のHaskellコード

instance (Eq (f (Cofree f a)), Eq a) => Eq (Cofree f a) where
  a :< as == b :< bs = a == b && as == bs

https://github.com/ekmett/free/blob/v4.2/src/Control/Comonad/Cofree.hs#L180-L181

その前に、そもそもCofreeのデータ型自体の定義を示していませんでしたね。Haskellだと以下の定義で

data Cofree f a = a :< f (Cofree f a)

これは、Scalaに直訳でき*2以下のようになります*3 *4

final case class Cofree[S[_], A](head: A, tail: S[Cofree[S, A]])


さて、HaskellでのEqのインスタンスの定義を直訳すると以下のようになります。定義するだけならエラーも出ずにうまくいったように見えますが、実際呼び出してみると「diverging implicit expansion」というエラーになって使えません。

implicit def cofreeEqual[A, F[_]](implicit A: Equal[A], F: Equal[F[Cofree[F, A]]]): Equal[Cofree[F, A]] =
  Equal.equal{ (a, b) =>
    A.equal(a.head, b.head) && F.equal(a.tail, b.tail)
  }

呼び出し側

scala> import scalaz._,Scalaz._
import scalaz._
import Scalaz._

scala> Cofree.cofreeEqual[Int, Option]
<console>:14: error: diverging implicit expansion for type scalaz.Equal[Option[scalaz.Cofree[Option,Int]]]
starting with method optionEqual in trait OptionInstances0
              Cofree.cofreeEqual[Int, Option]
                                ^


cofreeEqual自体は、implicitパラメータをとるimplicit defです。implicitパラメータの部分にまたCofreeが出現していて「自分自身を定義するのに、自分自身から生成されるimplicitなものが必要」という再帰的な構造になっています。これはScalaでは無理です。
(というか、むしろHaskellはなぜこれが可能なのでしょうか・・・。標準の範囲？GHC拡張？)



では、少し定義を変えてみましょう

implicit def cofreeEqual[A, B, F[_]](implicit A: Equal[A], F: Equal[B] => Equal[F[B]]): Equal[Cofree[F, A]] =
  Equal.equal{ (a, b) =>
    A.equal(a.head, b.head) && F.apply(Equal[Cofree[F, A]]).equal(a.tail, b.tail)
  } 

/*
core/src/main/scala/scalaz/Cofree.scala:149: type mismatch;
[error]  found   : scalaz.Equal[scalaz.Cofree[F,A]]
[error]  required: scalaz.Equal[B]
[error]       A.equal(a.head, b.head) && F.apply(Equal[Cofree[F, A]]).equal(a.tail, b.tail)
[error]                                               ^
*/

Equal[B] => Equal[F[B] ]というものさえあればいいわけです。(たとえば、List[A]のAのEqualが存在すれば、List[A]のEqualのインスタンスも生成できる、というように。)
上記の定義でうまくいくように見えます(?)がうまくいきません。型パラメータBはcofreeEqualを呼び出した際に固定されてしまい、cofreeEqualの内部でFに対してEqual[Cofree[F, A] ]を渡そうとしても、型が違うと怒られます。以下のようにしても同じくうまく行きません。

implicit def cofreeEqual[A, F[_]](implicit A: Equal[A], F: Equal[Cofree[F, A]] => Equal[F[Cofree[F, A]]]): Equal[Cofree[F, A]] = 
  Equal.equal{ (a, b) =>
    A.equal(a.head, b.head) && F.apply(Equal[Cofree[F, A]]).equal(a.tail, b.tail)
  } 

scala> Cofree.cofreeEqual[Int, List]
<console>:14: error: No implicit view available from scalaz.Equal[scalaz.Cofree[List,Int]] => scalaz.Equal[List[scalaz.Cofree[List,Int]]].
              Cofree.cofreeEqual[Int, List]
                                ^


さて、ここで以前紹介したNaturalTransformationの出番です*5
Scalaz の NaturalTransformation

結果的に以下のようになりました

implicit def cofreeEqual[A, F[_]](implicit A: Equal[A], F: Equal ~> ({type λ[α] = Equal[F[α]]})#λ): Equal[Cofree[F, A]] =
  Equal.equal{ (a, b) =>
    A.equal(a.head, b.head) && F(cofreeEqual[A, F]).equal(a.tail, b.tail)
  }

標題にRank2Typeとつけたのは、つまりこのことです。Scalaでこのようなことをする場合「単なるimplicit def」ではなく「型パラメータをとるメソッドがあるオブジェクト」をつかって、型パラメータの固定のタイミングを遅延させる必要があります。(もっといい解決策あったら教えて下さいコメントで教えてもらったとおり、shapelessのLazyはこういうときのためにあるのですね、なるほど・・・)
詳しくないので説明しないで逃げますが、これつまりRank2Typeですよね？NaturalTransformationのようなものを駆使しないとできないです。

さて、Scalaの言語仕様上、このようにCofreeのEqualのインスタンスを定義しても、たとえば以下のようにimplicit valでそれぞれNaturalTransformationの値を定義しないと拾ってくれないのでだいぶ面倒です。(これ以上短い構文でimplicit defからNaturalTransformationに変換できない)

implicit val lazyOptionEqualNat = new (Equal ~> ({type λ[α] = Equal[LazyOption[α]]})#λ){
  def apply[A](a: Equal[A]) = LazyOption.lazyOptionEqual(a)
}

でも無いよりはいいだろう、ということで一応定義しておきました。



数日前haskell-jpに投稿したのもCofreeの件ですが

ekmett/free の Cofree のインスタンスがバグってる？

自分の中でだいたい答えはでたので、ApplyやApplicativeはTagged Type(Haskellのnewtypeのようなもの)使って2種類定義してpull reqしました。

https://github.com/scalaz/scalaz/pull/610

これ書いてる12月23日現在まだmergeされてません。もしレビュー出来る人がいれば、ツッコミなどお待ちしています。



追記:
技術的にはたしかに可能でしたが、NaturalTransformationは型クラスではないので、「型クラスではないものをimplicitで使うべきではない」という原則に従い、後になって自分が入れたオリジナルのCofreeのEqualのインスタンスは削除されています

*1:googleさんが「もしかして？」も言わずに、cofreeで検索してもcoffeeの結果も出すので死んで欲しい

*2:以前からScalaz内に存在する https://github.com/scalaz/scalaz/blob/v7.1.0-M4/core/src/main/scala/scalaz/Cofree.scala#L4

*3:細かい部分は省略してる

*4:stack overflowを避けるために、最近Trampoline使った実装に変わったが、意味的には今でも以下のコードと同じ

*5:べつに、Forall https://github.com/scalaz/scalaz/blob/v7.1.0-M4/core/src/main/scala/scalaz/Forall.scala#L3-L6 でもいいが