Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- sealed trait Tree[+A]
- final case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
- final case class Leaf[A](value: A) extends Tree[A]
- implicit val treeMonad = new Monad[Tree] {
- override def pure[A](value: A): Tree[A] = Leaf(value)
- override def flatMap[A, B](initial: Tree[A])(func: A => Tree[B]): Tree[B] =
- initial match {
- case Branch(l, r) => Branch(flatMap(l)(func), flatMap(r)(func))
- case Leaf(value) => func(value)
- }
- //@tailrec
- override def tailRecM[A, B](a: A)(func: (A) => Tree[Either[A, B]]): Tree[B] = {
- func(a) match {
- case Branch(l, r) =>
- Branch(
- flatMap(l) {
- case Right(l) => pure(l)
- case Left(l) => tailRecM(l)(func)
- },
- flatMap(r){
- case Right(r) => pure(r)
- case Left(r) => tailRecM(r)(func)
- }
- )
- case Leaf(Left(value)) => tailRecM(value)(func)
- case Leaf(Right(value)) => Leaf(value)
- }
- }
- }
- override def tailRecM[A, B](a: A)(f: (A) => Tree[Either[A, B]]): Tree[B] = {
- @tailrec
- def go(toVisit: List[Tree[Either[A, B]]],
- toCollect: List[Tree[B]]): List[Tree[B]] = toVisit match {
- case (tree :: tail) =>
- tree match {
- case Branch(l, r) =>
- l match {
- case Branch(_, _) => go(l :: r :: tail, toCollect)
- case Leaf(Left(a)) => go(f(a) :: r :: tail, toCollect)
- case Leaf(Right(b)) => go(r :: tail, pure(b) +: toCollect)
- }
- case Leaf(Left(a)) => go(f(a) :: tail, toCollect)
- case Leaf(Right(b)) =>
- go(tail,
- if (toCollect.isEmpty) pure(b) +: toCollect
- else Branch(toCollect.head, pure(b)) :: toCollect.tail)
- }
- case Nil => toCollect
- }
- go(f(a) :: Nil, Nil).head
- }
Add Comment
Please, Sign In to add comment