やったこと

ミリシタ

TC最初のイベントのはじまり。
ちょっとだけやる気があるのだけど、目下の悩みはSSA。
あと2日とか実感がねえ。

シャニ

MVP取れた。
MVPのコミュ良かった。

https://twitter.com/make_now_just/status/1174629419610066945

今度は灯織で感謝祭していた。
ようやく星3ノートクリアできた。
しんどすぎるんじゃ。

https://twitter.com/make_now_just/status/1174638867267248128

https://twitter.com/make_now_just/status/1174640126384689154

daliのスライド

daliの開発はsbtがJDK 13で壊れた影響で完全に止まっている。
許せ‥‥。

というわけでスライドを公開した。

https://speakerdeck.com/makenowjust/dali-introduction

まあ大した内容ではないが。

implicit完全に理解した

迷ったときは仕様を読むと良い。

https://www.scala-lang.org/files/archive/spec/2.13/07-implicits.html#implicit-parameters

implicitな値の宣言がimplicitパラメータを持つとき、implicitな値は再帰的に探索されていく。
そこで見つかった型とその型を提供するimplicitな値の宣言はスタックに積まれる。
さらに、探索が無限ループに陥らないようにするため、スタックの状態によっては探索を打ち切る場合がある。
(探索を打ち切る=探索失敗ではないので注意)

• スタックに積もうとしてる型と等しい型があって、その型のあるスタック上の位置と先頭までの間にby nameな宣言がある場合、スタックのそこまでをlazy valでくくり出して、成功で探索を打ち切る。
• スタックに積もうとしてる型が支配する (dominateする)がスタック上にある場合、divergingとして失敗で探索を打ち切る。
• それ意外の場合、スタックに型と宣言を追加して、探索を継続する。

で、この「支配する」という条件が曲者で、詳細は次のようになっている。

型Tが型Uを支配するとはTとUが等しいか、TとUのトップレベルの型コンストラクタ(top-level type constructor)に等しい部分があり、TがUよりも複雑で、TとUのcovering setが等しいときのことをいう。

用語がいくつか出てきたのでさらに解説すると、

• トップレベルの型コンストラクタとは簡単に言うと、型パラメタを除いたり、シングルトン型を本来の型に戻したりしたもののこと。
  例えばList[Int]ならトップレベルの型コンストラクタはListだし"foo"ならStringになる。
• TがUよりも複雑であるとは、型の複雑性(整数値)がより大きいことをいう。
  型の複雑性は簡単に言うと、エイリアスなどを全て展開した上で、型に現れるパッケージ以外の名前の数を重複混みで数えたものとして考えればいいと思う。ただしシングルトン型は+ 1する。
  例えばList[Int]はList, Intなので複雑性は2、List[(Int, String, Int)]はList, Tuple3, Int, String, Intで複雑性は5、といった感じ。
• 型のcovering setとは、型に現れるパッケージ以外の名前の集合でいいと思う。
  例えばList[(Int, Int)]のcovering setはList, Tuple2, Intのような感じ。

ここまで理解すると、昨日のTreeのEqが導出できない理由が説明できる。

// List:
sealed trait List[A]
class Nil[A]
class Cons[A]

// Tree:
class Tree[A]

// HList:
sealed trait HList
class HNil extends HList
class :*:[H, T <: HList] extends HList

// Coproduct:
sealed trait Coproduct
class CNil extends Coproduct
class :+:[H, T <: Coproduct] extends Coproduct

// Generic:
trait Generic[A, R]

object Generic {
  implicit def list[A]: Generic[List[A], Nil[A] :+: Cons[A] :+: CNil] = ???
  implicit def nil[A]: Generic[Nil[A], HNil] = ???
  implicit def cons[A]: Generic[Cons[A], A :*: List[A] :*: HNil] = ???

  implicit def tree[A]: Generic[Tree[A], A :*: List[Tree[A]] :*: HNil] = ???
}

// Eq:
trait Eq[A]

object Eq {
  implicit def int: Eq[Int] = ???

  implicit def generic[A, R](implicit AR: Generic[A, R], R: GEq[R]): Eq[A] = ???
}

// GEq:
trait GEq[R]

object GEq {
  implicit val hnil: GEq[HNil] = ???
  implicit def hcons[H: GEq, T <: HList: GEq]: GEq[H :*: T] = ???
  implicit val cnil: GEq[CNil] = ???
  implicit def ccons[H: GEq, T <: Coproduct: GEq]: GEq[H :+: T] = ???

  implicit def value[A](implicit A: => Eq[A]): GEq[A] = ???
}

ここでimplicitly[Eq[Tree[Int]]]とすると、まずEq.genericを候補としてGEq[Int :*: List[Tree[Int]] :*: HNil]を探索しに行く。
探索が続くと最終的に、GEq[Cons[Tree[Int]]]の候補としてGEq.valueを見つけて、Eq[Cons[Tree[Int]]]を探索する。
この候補はEq.genericでGEq[Tree[Int] :*: List[Tree[Int]] :*: HNil]を見つける必要があるが、ここで最初のGEq[Int :*: List[Tree[Int]] :*: HNil]と複雑度、covering setを比較すると、

• GEq[Int :*: List[Tree[Int]] :*: HNil]の複雑度8、covering set GEq, :*:, HNil, List, Tree, Int
• GEq[Tree[Int] :*: List[Tree[Int]] :*: HNil]の複雑度 9、 covering set GEq, :*: HNil, List, Tree, Int

なので、divergingと判定され探索が打ち切られ、候補が見つけられず全体の探索が失敗する。

一応、ここまで理解していれば回避策を考えるのも簡単で、例えばTuple1を追加してGeneric.treeを修正すれば、

// Tuple1:
class Tuple1[A]

// Generic:
object Generic {
  // ...

  implicit def tree[A]: Generic[Tree[A], Tuple1[A] :*: List[Tree[A]] :*: HNil]

  implicit def tuple1[A]: Generic[Tuple1[A], A :*: HNil]
}

implicitly[Eq[Tree[Int]]]は動くようになる。
これはTuple1で囲ったことでcovering setが異なるものになったため。
しかしTuple1[List[Tree[A]]]としてはいけない。
なぜなら、これだとEq[Tuple1[List[Tree[Int]]]]を導出するときに探索するGEq[List[Tree[Int]] :*: HNil]が、Eq[Cons[Tree[Int]]]を導出するときに探索するGEq[Tree[Int] :*: List[Tree[Int]] :*: HNil]に支配されてしまい、divergingになってしまう。

また次の定義を追加しても動作する。

implicit def list[A: Eq]: Eq[List[A]] = Eq.generic

この定義を追加することでEq[Cons[Tree[Int]]]の探索が行なわれず、先にEq[Tree[Int]]の探索が行なわれ、これは最初の型と等しく間にGEq.valueによるby nameな値を含むため、正しく展開される。

ちなみにimplicitlyの展開結果などはreifyを使うと比較的簡単に確かめられる。
覚えておくと便利かもしれない。

import scala.reflect.runtime.universe.reify

println(reify(implicitly[Eq[Tree[Int]]]))
// Expr[Eq[Tree[Int]]](Predef.implicitly[Eq[Tree[Int]]]({
//   final class LazyDefns$1 {
//     final val rec$1 = Eq.generic(
//       Generic.tree,
//       GEq.hcons(
//         GEq.value(Eq.int),
//         GEq.hcons(
//           GEq.value(list(rec$1)),
//           GEq.hnil,
//         ),
//       ).
//     )
//   };
//   final val lazyDefns$1 = new LazyDefns$1();
//   lazyDefns$1.rec$1
// }))

上のはlistを定義したときの展開結果だけど、Tuple1を使うと以下のようになる。
いかにも完全に展開しました、という雰囲気がある。

println(reify(implicitly[Eq[Tree[Int]]]))
// Expr[Eq[Tree[Int]]](Predef.implicitly[Eq[Tree[Int]]]({
//   final class LazyDefns$1 {
//     final val rec$2 = GEq.hcons(
//       GEq.value(
//         Eq.generic(
//           Generic.list,
//           GEq.ccons(
//             GEq.value(Eq.generic(Generic.nil, GEq.hnil)),
//             GEq.ccons(
//               GEq.value(Eq.generic(Generic.cons, GEq.hcons(GEq.value(rec$1), rec$2))),
//               GEq.cnil,
//             ),
//           ),
//         ),
//       ),
//       GEq.hnil,
//     );
//     final val rec$1 = Eq.generic(
//       Generic.tree,
//       GEq.hcons(
//         GEq.value(Eq.generic(Generic.tuple1, GEq.hcons(GEq.value(Eq.int), GEq.hnil))),
//         rec$2,
//       ),
//     )
//   };
//   final <synthetic> val lazyDefns$1 = new LazyDefns$1();
//   lazyDefns$1.rec$1
// }))

ただ、Tuple1を使う方法だとTree[List[Int]]では展開が上手くいかないのでEq.genericを使ってEq[List[A]]を定義しておく方が無難な気がする。
(Eq[Tuple[List[Int]]]を導出するために探索するGEq[List[Int] :*: HNil]が、Eq[Cons[Int]]を導出するために探索するGEq[Int :*: List[Int] :*: HNil]に支配されてしまうため)

implicitへの理解度は上がったが、この知識がどこで役に立つのかは全く分からない。
あとScastie便利。