やったこと

ミリシタ

折り返し。早いなと思ったら一日短いらしい。

とりあえず10万ptまで稼いだけど、うーん。

Scala関連

型クラスの制約のエンコード方法について

ScalaでHaskellの型クラスの制約(Eq a => Ord aみたいなの)を表現するときに、Scalaでは2つの方法がある。

1つは継承を用いるもので、trait Ord[A] extends Eq[A]のようにする。
基本的にはこちらが一般的で、ほとんどの場合はこちらを利用する。

もう1つはメンバに制約の型クラスのインスタンスを持たせるもの。
このようになる。

trait Ord[A] {
  val eq: Eq[A]
}

これはcatsのParallelのように、そもそも継承として表せない場合や、
(これをtrait Parallel[F[_], G[_]] extends Applicative[F] with Monad[G]とするとFに対するmapとGに対するmapが衝突したりしてロクなことにならない)

trait Parallel[F[_], G[_]] {
  def applicative: Applicative[F]
  def monad: Monad[G]

  def sequence: F ~> G
  def parallel: G ~> F
}

或いは継承関係が複数に枝分かれしていて、implicitが曖昧になる場合に使われる。

implicitが曖昧になる場合

例えばFunctorであることを制約に持つ型クラスとしてApplicativeとTraverseがある。
これを単純に継承で表すとどのようなことが起こるだろうか。

trait Functor[F[_]] {
  def map[A. B](fa: F[A], f: A => B): F[B]
}

trait Applicative[F[_]] extends Functor[F] {
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
  def pure[A](a: A): F[A]
}

trait Foldable[F[_]] {
  def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B
  def foldRight[A, B](fa: F[A], b: B)(f: (A, B) => B): B
}

trait Traverse[F[_]] extends Foldable[F] with Functor[F] {
  def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
}

ここでApplicativeかつTraverseな型に対してはたらくようなメソッドで、Functorのメソッドであるmapを呼ぶようなものを考える。

def foo[F[_]: Applicative: Traverse, A, B](fa: F[A]) = implicitly[Functor[F]].map(fa)(a => ???)

これはコンパイルが通らない。
なぜならばFunctorのimplicitの候補がApplicativeのものとTraverseのもので2つあり、曖昧になっているからだ。

これは、次のようにfunctorをメンバにして、Functorを取り出す用のimplicit defを継承を使って優先順位を調整して定義すると良い。

trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

trait Applicative[F[_]] {
  def functor: Functor[F]
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
  def pure[A](a: A): F[A]
}

trait Foldable[F[_]] {
  def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B
  def foldRight[A, B](fa: F[A], b: B)(f: (A, B) => B): B
}

trait Traverse[F[_]] {
  def functor: Functor[F]
  def foldable: Foldable[F]
  def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
}

trait Extract extends ExtractFunctor with ExtractFoldable

trait ExtractFunctor extends ExtractFunctor0
trait ExtractFunctor0 extends ExtractFunctor1 {
  implicit def extractFunctorFromApplicative[F[_]: Applicative]: Functor[F] = Applicative[F].functor
}
trait ExtractFunctor1 {
  implicit def extractFunctorFromTraverse[F[_]: Traverse]: Functor[F] = Traverse[F].functor
}

trait ExtractFoldable {
  implicit def extractFoldableFromTraverse[F[_]: Traverse]: Foldable[F] = Traverse[F].foldable
}

object extract extends Extract

import extract._

これでひとまず問題は解決する。

さらなる話題

‥‥という話がこの辺に書かれている。

• Typelevel.scala | Subtype type classes don't work:

https://typelevel.org/blog/2016/09/30/subtype-typeclasses.html

• The Limitations of Type Classes as Subtyped Implicits

(Short Paper): https://adelbertc.github.io/publications/typeclasses-scala17.pdf

書いたのは同じ人で、下のPDFが上のやつの更新版、という感じ。

とはいえこのメンバにする方法(MTL encodingとかinheritance free encodingとかいう)も万能ではなくて、欠点として、

• まず見るからに記述量が増える。正直しんどい。
• 取り出す部分が拡張に対して開いていない。
  例えば別のライブラリでFunctorFilterが定義されたとして、それからFunctorを取り出すimplicit defをどうやって衝突しないように定義できるだろうか？

などの問題が挙げられる。

そんなこんなな理由からcatsでは基本的には継承を使い、いくつかの衝突しがちな型クラスではメンバに埋め込む方法を取っているらしい。

cats-mtlのGetting Startedにもこんなことが書いてあった。

If you’re wondering why ApplicativeAsk has an Applicative field instead of just extending from Applicative, that is to avoid implicit ambiguities that arise from having multiple subclasses of a given type (here Applicative) in scope implicitly. So in this case we favor composition over inheritance as otherwise, we could not e.g. use Monad together with ApplicativeAsk.

なので、基本的にはimplicitの衝突を回避する目的、ということでいいのだと思う。

ところでcats-mtlのこのあとの例で、implicitでMonadStateとMonadErrorしか取ってないのにMonadのメソッドが使えてる感じがする例があるのだけど、これはどういうことなんだろう？
どこからMonadのインスタンスを持って来てるんだ？

あとDotty (Scala 3)のgivenとdelegateもちょっと関係あるのかな、とか思ってるけど、その辺はよく分からない。
誰か詳しい人教えて。

その他気になる話

Typelevel.scala | A tale on Semirings: https://typelevel.org/blog/2018/11/02/semirings.html

これが気になっている。あとでちゃんと読もう。