Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Extensible Effects with Scala/eff-with-scala

fuzyco
April 13, 2018

Extensible Effects with Scala/eff-with-scala

Extensible Effectsの概要とScalaでの実装の説明です

fuzyco

April 13, 2018
Tweet

More Decks by fuzyco

Other Decks in Technology

Transcript

  1. 5ZQF-BNCEBT UZQF1BJS<"> " " UZQF1BJS<"> " " WBMQ1BJS<*OU>  

    %PUUZ 4DBMB <Ҿ༻IUUQTXXXTMJEFTIBSFOFU4BOTIJSP:PTIJEBFYUFOTJCMFF⒎FDUTJOEPUUZ>
  2. 5ZQF-BNCEBT type FreeMonad[F[_]] = Monad[({ type λ[A] = Free[F, A]

    })#λ] type FreeMonad[F[_]] = Monad[[A] => Free[F, A]] %PUUZ 4DBMB ܕͷ෦෼ద༻͕௚઀ॻ͚Δ <Ҿ༻IUUQTXXXTMJEFTIBSFOFU4BOTIJSP:PTIJEBFYUFOTJCMFF⒎FDUTJOEPUUZ>
  3. 6OJPO5ZQF val x: String | Int = if util.Random.nextBoolean() then

    "hoge" else 0 <Ҿ༻IUUQTXXXTMJEFTIBSFOFU4BOTIJSP:PTIJEBFYUFOTJCMFF⒎FDUTJOEPUUZ>
  4. Ϟφυม׵ࢠ case class User(id: Long, firstName: Option[String], lastName: Option[String]) def

    getUser(id: Long): Either[String, User] = ??? def getUserName(id: Long): Either[String, Option[String]] = for { user <- getUser(id) // Either } yield for { first <- user.firstName // Option last <- user.lastName } yield s"$first $last" import cats.data.OptionT import cats.implicits._ type StringEither = [A] => Either[String, A] def getUserName(id: Long): Either[String, Option[String]] = (for { user <- OptionT.liftF(getUser(id)) first <- OptionT.fromOption[StringEither](user.firstName) last <- OptionT.fromOption[StringEither](user.lastName) } yield s"$first $last").value GPS͕ࣜ࿈࠯ͯ͠ॻ͖ͮΒͯ͘ಡΈͮΒ͍ ෳ਺ͷϞφυ͕ࠞࡏ͢Δ৔߹ GPSࣜҰͭͰॻ͚Δ
  5. Ϟφυม׵ࢠͷ໰୊఺ ߹੒͢ΔϞφυ͕૿͑Δͨͼʹɺܭࢉͷޮ཰͕མͪΔ package cats package data final case class OptionT[F[_],

    A](value: F[Option[A]]) { def flatMap[B](f: A => OptionT[F, B])(implicit F: Monad[F]): OptionT[F, B] = flatMapF(a => f(a).value) def flatMapF[B](f: A => F[Option[B]])(implicit F: Monad[F]): OptionT[F, B] = OptionT(F.flatMap(value)(_.fold(F.pure[Option[B]](None))(f))) } ճϧʔϓ͕૸Δ
  6. Ϟφυม׵ࢠͷ໰୊఺ ԼҐͷϞφυͷॲཧΛߦ͏ͷʹɺҰʑMJGUΛߦ͏ඞཁ͕͋Δ import cats.data.{ OptionT, StateT } import cats.instances.list._ import

    cats.instances.either._ type StringEither = [A] => Either[String, A] type OptionTEither = [A] => OptionT[StringEither, A] type StateTOptionTEither[S, C, A] = StateT[[C] => OptionTEither[C], S, A] def getUser(id: Long): Either[String, User] = ??? def getState(id: Long): StateTOptionTEither[Int, User, Long] = StateT.liftF { OptionT.liftF { getUser(id) }.map { user => user.id } } ԼҐͷ&JUIFSͷॲཧΛߦ͏ͨΊʹɺ ೋճMJGUΛݺΜͰ͍Δ
  7. Ϟφυม׵ࢠͷ໰୊఺ Ϟφυͷ߹੒ॱ͸ݻఆ͞Ε͍ͯͯɺ్தͰೖΕସ͑Δ͜ͱ͕Ͱ͖ͳ͍ ϞφυΛ߹੒͢Δॱ൪ʹΑͬͯɺܭࢉͷҙຯ͕มΘΔ import cats.data.{OptionT, State, StateT} import cats.instances.either._ import

    cats.instances.option._ // StateT[Option, Int, Int] StateT.modify[Option, Int] { _+1 }.flatMap { _ => StateT.liftF[Option, Int, Int](None) }.run(10) // None type IntState = [A] => State[Int, A] // OptionT[IntState, Unit] OptionT.liftF[IntState, Unit] { State.modify{ _+1 } }.flatMap { _ => OptionT.none[IntState, Unit] }.value.run(10).value // (11, None) ԼҐͷϞφυ͕0QUJPOͳͷͰɺ ్தͰࣦഊ͢Δͱ/POFʹͳΔ ԼҐͷϞφυ͕4UBUFͳͷͰɺ ్தͰࣦഊͯ͠΋಺෦ঢ়ଶ͸อ࣋͞ΕΔ
  8. ࿩͢͜ͱ w 'SFF w 'SFFS w $PZPOFEB w 5ZQFBMJHOFE2VFVF w

    'BTU'SFFS w &YUFOTJCMF&⒎FDUT w 0QFO6OJPO
  9. 'SFF.POBE case class Pure[F[_], A](a: A) extends Free[F, A] case

    class Impure[F[_], A](ff: F[Free[F, A]]) extends Free[F, A] sealed trait Free[F[_], A] { def map[B](f: A => B)(implicit F: Functor[F]): Free[F, B] = flatMap(a => Pure(f(a))) def flatMap[B](f: A => Free[F, B])(implicit F: Functor[F]): Free[F, B] = this match { case Pure(a) => f(a) case Impure(ff) => { Impure(F.map(ff)(_.flatMap(f))) } } } def lift[F[_], A](fa: F[A])(implicit F: Functor[F]): Free[F, A] = Impure(F.map(fa)(a => Pure(a))) 'VODUPSΛϞφυʹม׵͢Δ ७ਮͳܭࢉ ෭࡞༻෇͖ͷܭࢉ
  10. 'SFF8SJUFS type Writer[W, A] = Free[[T] = Tell[W, T], A]

    // w: ग़ྗ஋ a: ܭࢉ͞Εͨ஋ case class Tell[W, A](w: W, a: A) { def map[B](f: A => B) = Tell(w, f(a)) } def tell[W](w: W): Writer[W, Unit] = Free.lift[[T] = Tell[W, T], Unit](Tell(w, ())) ܭࢉ͞Εͨ஋ͱ͸ผʹσʔλͷετϦʔϜΛੜ੒͢ΔϞφυ
  11. 'SFF8SJUFS type Writer[W, A] = Free[[T] = Tell[W, T], A]

    // w: ग़ྗ஋ a: ܭࢉ͞Εͨ஋ case class Tell[W, A](w: W, a: A) { def map[B](f: A => B) = Tell(w, f(a)) } def tell[W](w: W): Writer[W, Unit] = Free.lift[[T] = Tell[W, T], Unit](Tell(w, ())) def runAsList[W, A](free: Writer[W, A]): (List[W], A) = free match { case pure: Free.Pure[[T] = Tell[W, T], A] => (Nil, pure.a) case impure: Free.Impure[[T] = Tell[W, T], A] => runAsList(impure.ff.a) match { case (ws, a) => (impure.ff.w :: ws, a) } } val e = for { _ <- tell("hoge") _ <- tell("fuga") } yield () runAsList(e) // (List(hoge, fuga),()) 8SJUFS͕'VODUPSͰ͋Ε͹ɺ ϞφυʹͳΔ ܭࢉ͞Εͨ஋ʹͱ͸ผʹσʔλͷετϦʔϜΛੜ੒͢ΔϞφυ
  12. 'SFF8SJUFS implicit def tellFunctor[W] = new Functor[[A] = Tell[W, A]]

    { def map[A, B](fa: Tell[W, A])(f: A => B): Tell[W, B] = fa.map(f) } implicit def writerFunctor[W] = new Functor[[A] = Writer[W, A]] { def map[A, B](fa: Writer[W, A])(f: A => B): Writer[W, B] = fa.map(f) } 'VODUPSͷܕΫϥεΛ࣮૷͢Δඞཁ͕͋Δ
  13. 'SFF8SJUFS type Writer[W, A] = Free[[T] = Tell[W, T], A]

    case class Tell[W, A](w: W, a: A) { def map[B](f: A => B) = Tell(w, f(a)) } def tell[W](w: W): Writer[W, Unit] = Free.lift[[T] = Tell[W, T], Unit](Tell(w, ())) implicit def tellFunctor[W] = new Functor[[A] = Tell[W, A]] { def map[A, B](fa: Tell[W, A])(f: A => B): Tell[W, B] = fa.map(f) } implicit def writerFunctor[W] = new Functor[[A] = Writer[W, A]] { def map[A, B](fa: Writer[W, A])(f: A => B): Writer[W, B] = fa.map(f) } def runAsList[W, A](free: Writer[W, A]): (List[W], A) = free match { case pure: Free.Pure[({type F[T] = Tell[W, T]})#F, A] => (Nil, pure.a) case impure: Free.Impure[({type F[T] = Tell[W, T]})#F, A] => runAsList(impure.ff.a) match { case (ws, a) => (impure.ff.w :: ws, a) } } val e = for { _ <- tell("hoge") _ <- tell("fuga") } yield () runAsList(e) // (List(hoge, fuga),())
  14. 'SFF.BZCF type ConstUnit[A] = Unit type Maybe[A] = Free[ConstUnit, A]

    def some[A](a: A): Maybe[A] = Free.Pure[ConstUnit, A](a) def none[A]: Maybe[A] = Free.Impure[ConstUnit, A]((): ConstUnit[Maybe[A]]) def safeDiv(n: Int, d: Int): Maybe[Int] = if (d == 0) none else some(n / d) implicit val ConstUnitFunctor = new Functor[ConstUnit] { def map[A, B](fa: ConstUnit[A])(f: A => B): ConstUnit[B] = (): ConstUnit[B] } val r = for { n <- safeDiv(4, 2) m <- safeDiv(n, 0) // none } yield m def maybe[A](maybe: Maybe[A])(default: A): A = maybe match { case Pure(a) => a case Impure(()) => default } assert(maybe(r)(42) == 42) // r͕noneͳͷͰɺdefaultͷ42͕ద༻͞ΕΔ $POTU6OJU͕'VODUPSͳͷͰɺ ϞφυʹͳΔ
  15. 'SFFS.POBE 'VODUPSͷ੍໿ͳ͠ʹϞφυʹͳΔ case class Pure[F[_], A](a: A) extends Freer[F, A]

    case class Impure[F[_], A, B](fa: F[A], f: A => Freer[F, B]) extends Freer[F, B] sealed trait Freer[F[_], A] { def map[B](f: A => B): Freer[F, B] = flatMap(a => Pure(f(a))) def flatMap[B](f: A => Freer[F, B]): Freer[F, B] = this match { case Pure(a) => f(a) case Impure(fa, g) => Impure(fa, (a: Any) => g(a).flatMap(f)) } } object Freer { def lift[F[_], A](fa: F[A]): Freer[F, A] = Impure(fa, a => Pure[F, A](a)) } $PZPOFEBͱΏ͏NBQΛ࣋ͭߏ଄Λ'SFFʹՃ͑ͨ΋ͷ
  16. 'SFFS8SJUFS type Writer[W, A] = Freer[[T] = Tell[W, T], A]

    case class Tell[W, A](w: W, a: A) { def map[B](f: A => B) = Tell(w, f(a)) } def tell[W](w: W): Writer[W, Unit] = Freer.lift[[T] = Tell[W, T], Unit](Tell(w, ())) def runAsList[W, A, B](freer: Writer[W, A]): (List[W], A) = freer match { case pure: Freer.Pure[({type F[T] = Tell[W, T]})#F, A] => (Nil, pure.a) case impure: Freer.Impure[({type F[T] = Tell[W, T]})#F, A, B] => runAsList(impure.k(impure.fa.a)) match { case (ws, a) => (impure.fa.w :: ws, a) } } val e = for { _ <- tell("hoge") _ <- tell("fuga") } yield () runAsList(e) // (List(hoge, fuga),()) 8SJUFS͕'VODUPSͰͳͯ͘΋ɺ ϞφυʹͳΔ
  17. 'SFFS.BZCF type ConstUnit[A] = Unit type Maybe[A] = Freer[ConstUnit, A]

    def some[A](a: A): Maybe[A] = Pure[ConstUnit, A](a) def none[A]: Maybe[A] = Freer[ConstUnit, A]((): ConstUnit[Maybe[A]]) def safeDiv(n: Int, d: Int): Maybe[Int] = if (d == 0) none else some(n / d) val r = for { n <- safeDiv(4, 2) m <- safeDiv(n, 0) // none } yield m def maybe[A](maybe: Maybe[A])(default: A): A = maybe match { case Pure(a) => a case Impure((), _) => default } assert(maybe(r)(42) == 42) // r͕noneͳͷͰɺdefaultͷ42͕ద༻͞ΕΔ $POTU6OJU͕'VODUPSͰͳͯ͘΋ɺ ϞφυʹͳΔ
  18. 0QFO6OJPO sealed trait Union // ܕͷऴ୺Λද͢ sealed trait Void extends

    Union // ܕͷ࿨Λߏ੒͢Δ sealed trait :+:[F[_], U <: Union] extends Union case class Inl[F[_], A, U <: Union](fa: F[A]) extends (F :+: U) // == :+:[F, U] case class Inr[F[_], U <: Union](u: U) extends (F :+: U) // == :+:[F, U] type ListOrOption = Option :+: List :+: Void val option1: ListOrOption = Inr(Inl(List(1, 2))) ܕͷ࿨Λ࣮ݱ͢Δ
  19. .FNCFS trait Member[F[_], U <: Union] { // ϞφυΛߏ੒͢ΔF͔ΒUnionΛಘΔ def

    inject[A](f: F[A]): U } // ࠨଆ΁ͷຒΊࠐΈ implicit def left[F[_], U <: Union]: Member[F, F :+: U] = new Member[F, F :+: U] { def inject[A](f: F[A]): F :+: U = Inl(f) } // ӈଆ΁ͷຒΊࠐΈ implicit def right[F[_], G[_], U <: Union](implicit member: Member[F, U]): Member[F, G :+: U] = new Member[F, G :+: U] { def inject[A](f: F[A]): G :+: U = Inr(member.inject(f)) } 6OJPO΁஋ΛຒΊࠐΉͨΊͷܕΫϥε type ListOrOption = Option :+: List :+: Void val option1: ListOrOption = Inr(Inl(List(1, 2))) val option2: ListOrOption = Member[List, ListOrOption].inject(List(1, 2))
  20. &YUFOTJCMF&⒎FDUT trait Eff[U <: Union, A] { def map[B](f: A

    => B): Eff[U, B] = flatMap(a => Pure(f(a))) def flatMap[B](f: A => Eff[U, B]): Eff[U, B] = this match { case Pure(a) => f(a) case Impure(u, g) => Impure(u, g :+ f) } } case class Pure[U <: Union, A](a: A) extends Eff[U, A] case class Impure[U <: Union, A, B](u: U, f: Arrows[U, A, B]) extends Eff[U, B] ܕύϥϝʔλʹ6OJPOΛ࣋ͭ
  21. &⒎8SJUFS case class Writer[W](w: W) type U = Writer :+:

    Void implicit val w = Member[Writer, U] def tell[U <: Union, W] ( w: W)( implicit ev: Member[Writer, U]): Eff[U, Unit] = Eff.Impure(ev.inject(Writer(w)), Leaf((_: Any) => Eff.Pure(()))) def runWriter[U <: Union, W, A](eff: Eff[Writer :+: U, A]): Eff[U, (List[W], A)] = eff match { case Eff.Pure(a) => Eff.Pure((Nil, a)) case Eff.Impure(Inl(Writer(w: W)), k) => runWriter[U, W, A](k(w)) map { case (ws, a) => (w :: ws, a) } case Eff.Impure(Inr(r), k) => Eff.Impure(r, Leaf((a: Any) => runWriter(k(a)))) }
  22. &⒎3FBEFS case class Reader[I]() type U = Reader :+: Void

    implicit val r = Member[Reader, U] def ask[U <: Union, I](implicit ev: Member[Reader, U]): Eff[U, I] = Eff.lift[U, Reader, I](Reader[I]) def runReader[U <: Union, I, A](eff: Eff[Reader :+: U, A], i: I): Eff[U, A] = eff match { case Eff.Pure(a) => Eff.Pure(a) case Eff.Impure(Inl(Reader()), k) => runReader(k(i), i) case Eff.Impure(Inr(r), k) => Eff.Impure(r, Leaf((a: Any) => runReader(k(a), i))) }
  23. 8SJUFS 3FBEFS def run[A](eff: Eff[Void, A]): A = eff match

    { case Eff.Pure(a) => a } def e[U <: Union](implicit r: Member[Reader, U], w: Member[Writer, U]): Eff[U, Int] = for { _ <- Writer.tell(2) x <- Reader.ask[U, Int] _ <- Writer.tell(x + 1) } yield x type MonadStack = Reader :+: Writer :+: Void Eff.run(runWriter(runReader(e[MonadStack], 1))) // (List(2, 2),1)) ϞφυελοΫ ೋͭͷϞφυΛҰͭͷGPSࣜʹॻ͚Δ SVO3FBEFS SVO8SJUFS ҕৡ BTLϦΫΤετΛॲཧ UFMMϦΫΤετΛॲཧ QVSFͳܭࢉʹͳͬͨΒɺ SVOͰ݁ՌΛऔΓग़͢
  24. &⒎͕ղܾ͢Δ͜ͱ ߹੒͢ΔϞφυ͕૿͑Δͨͼʹɺܭࢉͷޮ཰͕མͪΔ ԼҐͷϞφυͷॲཧΛߦ͏ͷʹɺҰʑMJGUΛߦ͏ඞཁ͕͋Δ def e[U <: Union](implicit r: Member[Reader, U],

    w: Member[Writer, U]): Eff[U, Int] = for { _ <- Writer.tell(2) x <- Reader.ask[U, Int] _ <- Writer.tell(x + 1) } yield x ɾճϧʔϓ͕૸Βͳ͍ ɾMJGUΛߦ͏ඞཁ͕ͳ͍
  25. &⒎͕ղܾ͢Δ͜ͱ def e[U <: Union](implicit r: Member[Reader, U], w: Member[Writer,

    U]): Eff[U, Int] = for { _ <- Writer.tell(2) x <- Reader.ask[U, Int] _ <- Writer.tell(x + 1) } yield x type MonadStack1 = Reader :+: Writer :+: Void type MonadStack2 = Writer :+: Reader :+: Void assert(Eff.run(runWriter(runReader(e[MonadStack1], 1))) == (List(2, 2),1)) assert(Eff.run(runReader(runWriter(e[MonadStack2]), 1)) == (List(2, 2),1)) Ϟφυͷ߹੒ॱ͸ݻఆ͞Ε͍ͯͯɺ్தͰೖΕସ͑Δ͜ͱ͕Ͱ͖ͳ͍ ϞφυΛ߹੒͢Δॱ൪ʹΑͬͯɺܭࢉͷҙຯ͕มΘΔ ݺͼग़͢ଆͰ੍ޚ͢Δ
  26. 6OJPO5ZQF val x: String | Int = if util.Random.nextBoolean() then

    "hoge" else 0 EPUUZͩͱ6OJPO5ZQF͕දݱ͠΍͍͢ <Ҿ༻IUUQTXXXTMJEFTIBSFOFU4BOTIJSP:PTIJEBFYUFOTJCMFF⒎FDUTJOEPUUZ>
  27. &YUFOTJCMF&⒎FDUTJO%PUUZ val e: Eff[[T] => Reader[Int, T] | Writer[Int, T],

    Int] = for { x <- Reader.ask[Int] _ <- Writer.tell(x + 1) } yield x scala> run(runWriter(runReader(e, 0))) val res0: (Int, Int) = (1,0) ΑΓγϯϓϧͳهड़͕Մೳʹͳͬͨ def e[U <: Union](implicit r: Member[Reader, U], w: Member[Writer, U]) = ??? <Ҿ༻IUUQTXXXTMJEFTIBSFOFU4BOTIJSP:PTIJEBFYUFOTJCMFF⒎FDUTJOEPUUZ>