Extensible Effects in Dotty を読んだ

ぱっと分からなかったことのメモ。Freerが分かってないとこの記事は分からないはず。Freerについてのわかりにくい記事はこちら

FTCQの必要性

以下のようなコードを考える

def foo() = for {
  a <- Impure("I'm from foo!", Pure.apply)
  b <- Pure("b")
} yield b

def bar() = for {
  a <- foo()
  b <- foo()
} yield b

def baz() = for {
  a <- bar()
  b <- bar()
} yield b

bazは、実行されると、barの計算結果を知ろうとし、その過程でfooの計算結果を知ろうとする。しかしfooはまずImpureを返すので、bazはfooの計算結果を知ることはできない。bazの実行は中断される。bazからはImpure("I'm from foo!", ...)が返る。
これは以下のように脱糖できる。

def foo() =
  Impure("I'm from foo!", Pure.apply).flatMap { a => 
    Pure("b").map(b => b)
  }

def bar() =
  foo().flatMap { a =>
    foo().map(b => b)
  }

def baz() =
  bar().flatMap { a =>
    bar().map(b => b)
  }

bazを見ていく。外側のbarを簡約すると以下になる。

foo().flatMap { a =>
  foo().map(b => b)
}.flatMap { a =>
  bar().map(b => b)
}

さらに外側のfooを簡約すると以下になる。

Impure("I'm from foo!", Pure.apply).flatMap { a => 
  Pure("b").map(b => b)
}.flatMap { a =>
  foo().map(b => b)
}.flatMap { a =>
  bar().map(b => b)
}

bazの返り値を作るためには、これを簡約する必要がある。3回flatMapを簡約する必要がある。ただI’m from foo!を返すだけのために!
脱糖前のコードを見ると、I’m from foo!はコールスタックが3回積まれた場所から返っていることがわかる。コールスタックを積めば積むほど、その一番奥から値を返すのに必要なflatMapの回数が増える。
実世界のことを考える。あなたのチームはCLIアプリケーションを作っている。コードベースが混沌とするのを防ぐため、型シグネチャから関数が純粋かそうでないかを判断できるようにしたい。あなたはEnvEffというのを用意し、環境変数はこのEff経由でのみ読んでくれとチームに伝えた。ところがある時、コールスタックの奥の奥から環境変数を読みたくなった。コールスタックを100積んだ場所から環境変数を読みたい。しかしそのためにはflatMapを100回実行する必要がある!流石にパフォーマンスが気になる。あなたはEffを導入したことを後悔する。
という事態を防ぐために、flatMapを高速化するためのものがFTCQだと思う。スライドにはIt is implemented with a treeと書いてあったが、Scalaで一番ポピュラーなEffの実装だと、Internally it is represented as a Vector of functionsらしい。どっちが良いんだろう。treeで表す必要性が理解できなかった。私、気になります!

Open Union

enum Union[F[_], G[_], A] {
  case Inl(value: F[A])
  case Inr(value: G[A])
}

Union seems to be a higher-kinded type version of Either、それは確かにそうなんだが、Eitherだと思ってこのコードを読んでも何も理解できなかった。これは型コンストラクタのユニオン。
型のユニオンはおなじみInt | Stringみたいなやつですね。パターンマッチでIntなのかStringなのかを確定して初めて値を取り出せる。型コンストラクタのユニオン、つまりスライドで言うOpen Unionは、List ||| Vectorみたいなもの。記号は適当。List ||| Vectorはそれ自体が型引数を一つ取る型コンストラクタ。例えば型引数としてIntを渡せる。(List ||| Vector)[Int]。これでList[Int]もしくはVector[Int]の値を取る型を表現する。あとは普通のユニオンと同じようにパターンマッチでList[Int]なのかVector[Int]なのかを確定すれば値を取り出せる。
|||なんて機能はScalaにはないので、自分で実装する必要がある。その実装がスライドに出てくるUnion。

スライドのUnionを使ってさっきのList ||| Vector(List ||| Vector)[Int]を表現してみる。

type ListOrVector[A] = Union[List, Vector, A]
type IntListOrIntVector = ListOrVector[Int]

Union[List, Vector, A]型がList[A]もしくはVector[A]型の値を取ることがUnionの定義のcase句で表現されている。よかったですね。
これで「2つの型コンストラクタのうちどちらか」を表現できた。次は「n個の型コンストラクタのうちのどれか」を表現する。とはいっても同じUnionでできる。分かりやすい?ように命名し直すと以下。Carは値を保持し、Cdrは値を保持しているUnionを保持する。リストと違ってCdrの指す先はCarとCdrを両方保持せず、そのどちらかであることに注意。それもうcdrじゃ無いじゃんという気がするが、他に名前を思いつかなかった

enum Union[Head[_], Tail[_], A] {
  case Car(value: Head[A])
  case Cdr(union: Tail[A])
}

ポイントは、HeadとTailを部分適用したUnionは型引数を一つ取る型コンストラクタなので、Tailに入ること。具体的にArray ||| List ||| Vector相当の物を表現したのが以下。

type ArrayOrListOrVector[A] = Union[
  Array,
  [A] => Union[
    List,
    [A] => Union[Vector, Nothing, A],
    A
  ],
  A
]
type IntArrayOrIntListOrIntVector = ArrayOrListOrVector[Int]

改めて書くとわけわからん。IntArrayOrIntListOrIntVectorの動きを順に追っていく。UnionがCar値コンストラクタを取るときは、それはHead[A]型の値を保持する。具体化するとArray[Int]。これは簡単。ややこしいのはCdr。Cdr値コンストラクタを取るときは、それはTail[A]型の値を保持する。具体化すると([A] => Union[List, [A] => Union[Vector, Nothing, A], A])[Int]。簡約するとUnion[List, [A] => Union[Vector, Nothing, A], Int]。ここまでで、IntArrayOrIntListOrIntVectorが、Array[Int]もしくはUnion[List, [A] => Union[Vector, Nothing, A], Int]型の値を取ることが分かった。

では、Union[List, [A] => Union[Vector, Nothing, A], Int]はどんな型の値を取るだろうか?Car値コンストラクタを取った場合、それはHead[A]型の値を保持する。具体化すると、List[Int]。Cdr値コンストラクタを取った場合、それはTail[A]型の値を保持する。具体化すると、([A] => Union[Vector, Nothing, A])[Int]。簡約すると、Union[Vector, Nothing, Int]Union[Vector, Nothing, Int]についても同じように考えてみてほしい。まとめると、以下のようになる。

たしかにIntArrayOrIntListOrIntVectorはArray[Int]型の値を保持する場合とList[Int]型の値を保持する場合とVector[Int]型の値を保持する場合があるようだ。すごい。

ん?Nothing[Int]Nothingは型コンストラクタじゃなくない? -> なんとNothingは型コンストラクタだった



Nothing[Int]型の値は存在しないので、Cdrの終点として使うのに最適。

ところで、

Union[
  Array,
  [A] => Union[
    List,
    [A] => Union[Vector, Nothing, A],
    A
  ],
  A
]

めちゃくちゃ書きにくい。さっきみたいにArray ||| List ||| Vectorと書けたらうれしい。それをやるための演算子を定義する。

type :+:[Head[_], Tail[_]] = [A] => Union[Head, Tail, A]

// 使い方
type ArrayOrListOrVector[A] = (Array :+: List :+: Vector :+: Nothing)[A]
type IntArrayOrIntListOrIntVector = ArrayOrListOrVector[Int]

リストの終端がNilなのと同じ要領で終端のマーカーとしてNothingを使っている。
注意点は、Scalaだと:で終わる演算子は右結合なので、優先順位が(Array :+: (List :+: (Vector :+: Nothing)))になること。簡約すると、上記の読みにくい型になるはずだ。ところで中置型コンストラクタって演算子と呼んでいいんだろうか

ところで、TailにUnionしか代入しないならそれを型制約で表現するべきなんじゃないのかと思ったが、頭が悪いのでScalaの型システムでそれをやる方法が思いつかない。誰か思いついたら教えて

Member

Memberの話をする前にEffの定義を確認する。FTCQを使った最適化を施さない場合、Effの定義は(多分)以下でいい。

type Eff[U[_], A] = Freer[U[_], A]

Freerの名前が変わっただけ。Union型をFreerに突っ込むとEffになる。やったぜ。ここで問題になるのがImpureの作り方。例えばスライドに出てきたFreer Reader。これのImpureの作り方を見てみる。

case class Ask[I, A](k: I => A)
def ask[I]: Freer[[A] => Ask[I, A], I] = Impure(Ask(identity), Pure.apply)

スライドのコード片をちょっと簡約した。askがAskをImpureに突っ込んでいる。ここでaskのEffバージョンを考える。ImpureにAskを直接突っ込むことはできない。Impureに突っ込むべきなのはAskになりうるUnion型だ。じゃあAskにしかならないUnionを作ればいいじゃないか、と思うかも知れない。

def ask[I]: Eff[([A] => Ask[I, A]) :+: Nothing, I]

これはこれで問題がある。そもそもEffは複数のFreerを同時に使うためのものだ。このaskでは、複数のFreerを同時に使うことができない。

for {
  config <- ask
  _ <- tell("aba")
} yield config

tell、Writerっぽい。tellの返り値の型はわからないが、少なくともAskにしかならないUnion型のEffではないだろう。同じfor式内の<-の右辺の型は同じ型コンストラクタからできている必要があるので、これは型チェックを通らない。型チェックを通すためにこの時askが返すべきなのは、tellの返り値の型もしくはAskになりうるUnion型のEff。つまり、askの返り値の型は、askが他にどんなEffと一緒に使われるかによって変わる必要がある。なので、askがどんなUnion型のEffを返すかは外部から指定できるようになっている必要がある。

def ask[U[_], I]: Eff[U, I]

これはこれで自由すぎる。askの仕事はAskの情報を含んだImpureを生成することなのだから、askの返り値の型は、AskになりうるUnion型のEffであるべきだ。単なるUnion型ではなく、”Askになりうる” Unionを型制約として記述できる必要がある。

それを実現するために、まずMemberという型クラスを仮定してみる。Member[Ask, U]のインスタンスが存在するならUはAskになりうるという仮定を置く。すると、askのEffバージョンは以下のように書ける。

def ask[U[_], I](implicit ev: Member[[A] => Ask[I, A], U]): Eff[U, I]

そうだね

次はその仮定を実装する。Union型は、Union型のTailにUnion型が入ることで、型システムの中で型コンストラクタのリストのような構造を織り成す。ここが自分がスライドを読んでいて一番混乱したポイントなのだが、このUnion型は値のレベルではユニオンっぽいが型のレベルだとリストっぽいのだ。Union型は、型コンストラクタのリストとして自身を見た時のいずれかの要素に型引数を適用した結果の型の値を取る。つまり「UはAskになりうる」というのは「型コンストラクタのリストUの要素として型コンストラクタAskが存在する」と同義。なので、Member[Ask, U]のインスタンスが存在するなら型コンストラクタのリストUの要素として型コンストラクタAskが存在する、ということが言えれば良い。implicit parameterの再帰的な探索を使って、型クラスのインスタンスを帰納的に定義することで、これを実現する。これ最初見た時マジかとなった Scala強い

trait Member[F[_], U[_]]

implicit def baseCase[Head[_], Tail[_]]: Member[Head, Head :+: Tail] =
  new Member[Head, Head :+: Tail] {}

implicit def recursiveCase[Needle[_], Head[_], Tail[_]]
(implicit ev: Member[Needle, Tail]): Member[Needle, Head :+: Tail] =
  new Member[Needle, Head :+: Tail] {}

Scalaよくわからないが、implicit defの型引数はforallっぽい働きをするっぽい。FにはAskとかが入ると思ってくれ。Head、Needleは普通の型コンストラクタ。TailはUnion。つまり型コンストラクタのリスト。

まずは基底部を見ていく。Member[Head, Head :+: Tail]のインスタンスを作っている。どういう意味だろうか。このimplicit defは、Headが先頭である型コンストラクタのリストにはHeadが含まれるということを言っている。自明ですね。基底部っぽい。

次にノット基底部を見ていく。この型シグネチャは、Tailの要素であるNeedleは、Tailの先頭に任意の型コンストラクタを追加したリストにも含まれる、と言っている。これまた自明な感じがする。

帰納法パワーは凄くて、この自明な定義2つだけで、さっきの「Member[F, U]のインスタンスが存在するなら型コンストラクタのリストUの要素として型コンストラクタFが存在する」を言えるようになる。具体例を見ていく。

implicitly[Member[Array, Array :+: List :+: Vector :+: Nothing]]

これはMemberのインスタンスの探索に成功する。baseCaseが引っかかる。

implicitly[Member[List, Array :+: List :+: Vector :+: Nothing]]

これはMemberのインスタンスの探索に成功する。まずはじめにrecursiveCaseに引っかかり、NeedleがList、HeadがArray、TailがList :+: Vector :+: Nothingになる。recursiveCaseはMember[Needle, Tail]のインスタンスを要求する。具体化するとMember[List, List :+: Vector :+: Nothing]。そしてこれがbaseCaseに引っかかる。

implicitly[Member[Vector, Array :+: List :+: Vector :+: Nothing]]

これはMemberのインスタンスの探索に成功する。まずはじめにrecursiveCaseに引っかかり、NeedleがVector、HeadがArray、TailがList :+: Vector :+: Nothingになる。recursiveCaseはMember[Needle, Tail]のインスタンスを要求する。具体化するとMember[Vector, List :+: Vector :+: Nothing]。そしてこれがrecursiveCaseに引っかかる。NeedleがVector、HeadがList、TailがVector :+: Nothingになる。recursiveCaseはMember[Vector, Vector :+: Nothing]のインスタンスを要求する。そしてこれがbaseCaseに引っかかる。

implicitly[Member[Option, Array :+: List :+: Vector :+: Nothing]]

これはMemberのインスタンスの探索に失敗する。まずはじめにrecursiveCaseに引っかかり、NeedleがOption、HeadがArray、TailがList :+: Vector :+: Nothingになる。recursiveCaseはMember[Option, List :+: Vector :+: Nothing]のインスタンスを要求する。そしてこれがrecursiveCaseに引っかかる。NeedleがOption、HeadがList、TailがVector :+: Nothingになる。recursiveCaseはMember[Option, Vector :+: Nothing]のインスタンスを要求する。これはrecursiveCaseに引っかかる。NeedleがOption、HeadがVector、 TailがNothingになる。これ以上探索を進められない。探索が終了する。アハ体験

これでaskの型シグネチャを書くことができた。askの実装を書くことはできるだろうか。askはAskになりうる任意のUnion型の値で、かつAskの情報を含む値を作る必要がある。(Ask :+: List :+: Nothing)[String]型の値も(Array :+: Vector :+: Ask :+: Nothing)[Int]型の値も同じ方法で作れる必要がある。難しそう。Memberに手を加えるとできる。

trait Member[F[_], U[_]] {
  def lift[A](effect: F[A]): U[A]
}

implicit def baseCase[Head[_], Tail[_]]: Member[Head, Head :+: Tail] =
  new Member[Head, Head :+: Tail] {
    def lift[A](effect: Head[A]): (Head :+: Tail)[A] = Car(effect)
  }
  
implicit def recursiveCase[Needle[_], Head[_], Tail[_]]
(implicit ev: Member[Needle, Tail]): Member[Needle, Head :+: Tail] =
  new Member[Needle, Head :+: Tail] {
    def lift[A](effect: Needle[A]): (Head :+: Tail)[A] = Cdr(ev.lift(effect))
  }

このコードを理解するために、以前挙げた(Array :+: List :+: Vector :+: Nothing)[Int]の取りうる値のまとめを思い出す。
- Carの場合: Array[Int]
- Cdrの場合:
- CdrがCarを保持する場合: List[Int]
- CdrがCdrを保持する場合:
- Cdrの保持するCdrがCarを保持する場合: Vector[Int]
- Cdrの保持するCdrがCdrを保持する場合: Nothing[Int]

法則は、
- 値はCarに包まれている必要がある
- Union型を型コンストラクタのリストとして見たときのn個目の要素である型コンストラクタの値を取りたい場合、Carをn回Cdrに包む必要がある (nは0始まりとする)

といったところだろうか。この処理を全てのUnion型に対して実装するために、同じようにimplicit parameterの再帰的な探索を使っている。

まず基底部を見ていく。Head[A]型の値をHeadを先頭とするUnion型の値にキャストする場合、ただ単にCarに包めばいいと書いてある。Array :+: List :+: Vector :+: Nothingの例で具体化すると、HeadはArrayだ。(Array :+: List :+: Vector :+: Nothing)[Int]型がArray[Int]の値を保持するのはCarにArray[Int]の値がくるまれている場合だったので、これは先程の例と一致する。

次にノット基底部を見ていく。TailにNeedleが含まれている場合、Needle[A]型の値を(Head :+: Tail)[A]型の値にキャストするには、まずNeedle[A]型の値をTail[A]型の値にキャストし、その結果をCdrにくるめばいいと書いてある。List[Int](Array :+: List :+: Vector :+: Nothing)[Int]にキャストする例で具体化すると、HeadがArray、NeedleがList、TailがList :+: Vector :+: Nothingだ。まずList[Int](List :+: Vector :+: Nothing)[Int]にキャストする。基底部の定義より、それはList[Int]型の値をCarにくるむことで実現できる。そしてその結果をCdrにくるむ。結果として、List[Int]をCarにくるんだものをCdrにくるんだものが出来上がる。先程の例では「CdrがCarを保持する場合: List[Int]」だったので、一致する。

これで、Askの値からAskになりうる任意のUnion型の値へのキャストができるようになった。askのEffバージョンを実装できる。

def ask[U[_], I](implicit ev: Member[[A] => Ask[I, A], U]): Eff[U, I] = Impure(ev.lift(Ask(identity)), Pure.apply)

askのEffバージョンを実装できた!🎉
tellのEffバージョンも実装してみよう。

case class Tell[W, A](w: W, k: Unit => A)
def tell[U[_], W](w: W)(implicit ev: Member[[A] => Tell[W, A], U]): Eff[U, Unit] =
  Impure(ev.lift(Tell(w, x => ())), Pure.apply)

これで、以下のコードが型チェックを通るようになる。

type Effects = ([A] => Ask[Int, A]) :+: ([A] => Tell[String, A]) :+: Nothing
val readAndWrite: Eff[Effects, Int] = for {
  _ <- tell[Effects, String]("start!")
  number <- ask[Effects, Int]
  result = number + 1
  _ <- tell[Effects, String]("finish!")
} yield result

やったぜ。ReaderモナドっぽいものとWriterモナドっぽいものを一つのfor式の中で一緒に使えている!🎉

とは言ってもまだflatMapの挙動を定義していない。定義したいが、単純にEff[([A] => Ask[Int, A]) :+: ([A] => Tell[String, A]) :+: Nothing, Hoge]のflatMapの挙動を定義すればいいわけではない。AskのflatMapの挙動とTellのflatMapの挙動からそれらを組み合わせて使った時のflatMapの挙動を導く必要がある。それが合成可能なモナドということだと思う。なので、ひとまずEffのことは忘れて、Ask単体のFreerのflatMapの挙動を考える。FreerはflatMapの挙動を外から注入できるモナドだった。

def runReader[I, A](freer: Freer[[A] => Ask[I, A], A], injection: I): A =
  freer match {
    case Pure(a) => a
    case Impure(Ask(continueWith), continuation) => 
      runReader(continuation(continueWith(injection)), injection)
  }

Impureの場合、つまり値の注入を要求された場合は、そこの継続にinjectionを引数として与えて呼び出す。そしてその結果がImpureなら同じことをする。というのを、Pureが見つかるまで繰り返す。runReaderの返り値はPureにくるまれていた値になる。

これのEffバージョンを考える。flatMapの挙動を注入する対象は、Askではなく、AskになりうるUnion型だ。そのUnion型がAsk以外の値を取った場合のことはひとまず考えないものとする。

def runReader[Tail[_], I, A]
(eff: Eff[([A] => Ask[I, A]) :+: Tail, A], injection: I): Eff[Tail, A] =
  eff match {
    case Pure(a) => Pure(a)
    case Impure(Car(Ask(continueWith)), continuation) =>
      runReader(continuation(continueWith(injection)), injection)
    case Impure(Cdr(_), _) => throw new Error("考えない")
  }

大体はさっきのと同じだが、返り値の型が計算結果の型AではなくEffになっている。これはAsk以外にflatMapの挙動を注入する対象がまだ残っている可能性があるから。例えばさっきの例だとTell。残っていると言っても、AskのflatMapの挙動の注入は既に終わっているので、それを型で表現したい。なので、処理対象のUnion型を、それを型コンストラクタのリストとして見た時にAskが先頭になっているものに限定し、返り値の型をEff[処理対象のUnion型, A]ではなく、Eff[処理対象のUnion型のTail, A]にした。

同じようにrunWriterを定義してみる。

def runWriter[Tail[_], W, A]
(eff: Eff[([A] => Tell[W, A]) :+: Tail, A]): Freer[Tail, (List[W], A)] =
  eff match {
    case Pure(a) => Pure((Nil, a))
    case Impure(Car(Tell(log, continueWith)), continuation) =>
      runWriter(continuation(continueWith(()))).map {
        case (logAcc, a) => (log :: logAcc, a)
      }
    case Impure(Cdr(_), _) => throw new Error("考えない")
  }

Pureに当たるまでコールスタックを積んで、Pureに当たったらコールスタックを溶かしながら各ログ出力をまとめて一つのリストを作っている。

さて、さすがにthrow new Errorするのはダメなので、そこを考えないといけない。例えば、runReaderがTellに当たったら、runWriterに処理を移譲して、ログの管理をやってもらいたい。しかし、そのことをrunReaderにハードコートしてはいけない。runReaderはAskのflatMapの挙動を定義するものであったはずだ。Ask以外のエフェクトに当たった時の挙動をハードコートしようとすれば、runReaderはAskと一緒に使われうる全てのエフェクトに対して関心を持たないといけなくなる。それでは合成可能性がオジャンになってしまう。Tellに当たった際にrunWriterに処理を移譲する、ということを、runReaderに書かずに実現する必要がある。答えを書くと、こんな感じらしい。

def runReader[Tail[_], I, A]
(eff: Eff[([A] => Ask[I, A]) :+: Tail, A], injection: I): Eff[Tail, A] =
  eff match {
    case Pure(a) => Pure(a)
    case Impure(Car(Ask(continueWith)), continuation) =>
      runReader(continuation(continueWith(injection)), injection)
    case Impure(Cdr(anotherEffect), continuation) =>
      Impure(anotherEffect, x => runReader(continuation(x), injection))
  }

def runWriter[Tail[_], W, A]
(eff: Eff[([A] => Tell[W, A]) :+: Tail, A]): Eff[Tail, (List[W], A)] =
  eff match {
    case Pure(a) => Pure((Nil, a))
    case Impure(Car(Tell(log, continueWith)), continuation) =>
      runWriter(continuation(continueWith(()))).map {
        case (logAcc, a) => (log :: logAcc, a)
      }
    case Impure(Cdr(anotherEffect), continuation) =>
      Impure(anotherEffect, x => runWriter(continuation(x)))
  }

runReaderがAsk以外のエフェクトに当たった時、runReaderは処理を終了し、Impureを返す。そのImpureは、継続しようとするとrunReaderが呼び出されるようになっている。これは次のように使う。

def run[A](eff: Eff[Nothing, A]): A = (eff: @unchecked) match {
  case Pure(a) => a
}

val (result, log) = run(runWriter(runReader(readAndWrite, 123)))

Eff[Nothing, A]のImpureにはNothing[A]型の値が入るが、この値は存在しないので、この場合Impureは存在できない。なのでパターンマッチの際に無視している。

readAndWriteには、tell、ask、tellという順番でエフェクトが並んでいる。なのでまずはじめに、runReaderはTellに出くわす。runReaderはImpureを返し、処理を終了する。このImpureは、継続しようとするとrunReaderが呼び出されるようになっている。次にrunWriterが呼び出され、先程runReaderが処理しなかったTellに出くわす。runWriterはTellを処理できるので、処理しようとする。runWriterがログをまとめるのはPureが見つかった後なので、Pureを見つけるために継続を呼び出す。その継続の実態はrunReaderなので、runReaderが呼ばれる。runReaderがtellの継続を()を引数として呼び出す。その結果、askが呼び出され、AskのImpureが返る。runReaderはそのAskのImpureに対してrunReaderを再帰的に呼び出す。runReaderはAskを処理できるので、継続をinjectionを引数として呼び出す。そしてその結果に対してrunReaderを再帰的に適用する。だが今度はAskではなくTellに当たる。runReaderはImpureを返し、処理がrunWriterに戻る。このImpureは、継続しようとするとrunReaderが呼び出されるようになっている。runWriterはrunWriterを再帰的に呼び出す。runWriterはTellを処理できるので、処理しようとする。runWriterがログをまとめるのはPureが見つかった後なので、Pureを見つけるために継続を呼び出す。その継続の実態はrunReaderなので、runReaderが呼ばれる。runReaderがtellの継続を()を引数として呼び出す。その結果Pureが返る。runReaderはPureに対してrunReaderを再帰的に適用する。runReaderはPureを返し、処理がrunWriterに戻る。runWriterはrunWriterを再帰的に呼び出す。runWriterはPureを返し、処理がrunに移る。runはPureにくるまれていた値を返す。終了。

これ考えた人頭おかしい。それとも自分の頭が手続き型だからややこしく感じるだけで、頭が関数型な人はぱっと理解できるんだろうか。わからん。というわけで、ReaderモナドとWriterモナドを一緒に使うことができた!🎉

ScastieからDottyサポートがなくなっていた… dotrにコピペすると動くはず