Путать о свободном поднятии монады и интерпретаторе, пример реализации dsl двоичного дерева - PullRequest
Новая
       29

Путать о свободном поднятии монады и интерпретаторе, пример реализации dsl двоичного дерева

2 голосов
/ 16 мая 2019

Я слежу за статьей scala без стеков со свободными монадами и пытаюсь написать свой собственный код.

функция и общий тип данных всегда смущали меня при поднятии 

sealed trait Free[F[_], A] {
  import Free._
  def map[B](f: A => B): Free[F, B] = flatMap(f andThen (Done(_)))
  def flatMap[B](f: A => Free[F, B]): Free[F, B] = FlatMapped(this, f)
  /** flatMap 别名 */
  final def >>=[B](f: A => Free[F, B]): Free[F, B] = this flatMap f
  final def fold[B](r: A => B, s: F[Free[F, A]] => B)(implicit F: Functor[F]): B = resume.fold(s, r)

  final def go(f: F[Free[F, A]] => Free[F, A])(implicit F: Functor[F]): A = {
    @tailrec def loop(t: Free[F, A]): A = t.resume match {
      case Left(s) => loop(f(s))
      case Right(r) => r
    }
    loop(this)
  }

  @tailrec
  final def resume(implicit F: Functor[F]): Either[F[Free[F, A]], A] = this match {
    case Done(a) => Right(a)
    case Suspend(s) => Left(F.map(s)(Done(_)))
    case FlatMapped(sub, f) => sub match {
      case Done(a) => f(a).resume
      case Suspend(s) => Left(F.map(s)(f))
      case FlatMapped(d, g) => d.flatMap(dd => g(dd).flatMap(f)).resume
    }
  }
}

object Free {

  def point[F[_], A](value: A): Free[F, A] = Done[F, A](value)
  def liftF[F[_], A](value: F[A]): Free[F, A] = Suspend(value)

  implicit val f0Functor: Functor[Function0] = new Functor[Function0] {
    override def map[A, B](a: () => A)(f: A => B): () => B = () => f(a())
  }

  final case class Done[F[_], A](a: A) extends Free[F, A]
  final case class Suspend[F[_], A](s: F[A]) extends Free[F, A]
  final case class FlatMapped[F[_], E, A](a: Free[F, E], f: E => Free[F, A]) extends Free[F, A]
}

вот мой собственный dsl о бинарном дереве 

  trait BTree[T]
  case class L[T](v: T) extends BTree[T]
  case class B[T](left: BTree[T], right: BTree[T]) extends BTree[T]

  trait BTreeFunctor[A]
  final case class BTDeepMapping[A](value: A) extends BTreeFunctor[A]

  type TreeDsl[A] = Free[BTreeFunctor, A]

  def lift[T](a: T): TreeDsl[T] = Free.liftF(BTDeepMapping[T](a))

  implicit val treeDslFunctor: Functor[BTreeFunctor] = new Functor[BTreeFunctor] {
    override def map[C, D](a: BTreeFunctor[C])(f: C => D): BTreeFunctor[D] = {
      a match {
        case BTDeepMapping(v) => BTDeepMapping(f(v))
      }
    }
  }

  def treeMap[A, B](treeDsl: TreeDsl[A => B], tree: BTree[A]): BTree[B] =
    treeDsl.resume.fold({
      case BTDeepMapping(a) => treeMap(a, tree)
    }, _ => tree)

  def map[A, B](a: BTree[A])(f: A => B): BTree[B] = treeMap(lift(f), a)

и демонстрационный код: 

val t: BTree[Int] = B(B(L(1), L(2)), L(3))
val expected = B(B(L(2), L(4)), L(6))
val actual = TreeFreeMonad.map(t)(_ * 2)

библиотека cats может быть намного проще, например 

object Tree {
  implicit val treeFunctor: Functor[Tree] =
    new Functor[Tree] {
      override def map[A, B](fa: Tree[A])(f: A ⇒ B): Tree[B] =
        fa match {
          case Branch(l, r) ⇒ Branch(map(l)(f), map(r)(f))
          case Leaf(v)      ⇒ Leaf(f(v))
        }
    }
}

Как я могу исправить реализацию map, я неправильно понял?

...