RecursionSchemeExample.scala

package shajra.learn


import shajra.learn.typeclass.Functor
import shajra.learn.typeclass.Functor.Syntax._


trait Mu[F[_]] {

  def fold[X](k: F[X] => X): X

  def toNu(implicit ev: Functor[F]): Nu[F] =
    fold[Nu[F]] { fnu =>
      new Nu[F] {
        type A = F[Nu[F]]
        val a = fnu
        def unfold(_a: A) =
          _a map { nuF =>
            nuF.unfold(nuF.a) map { x =>
              new Nu[F] {
                type A = nuF.A
                val a = x
                def unfold(__a: A) = nuF.unfold(__a)
              }
            }
          }
      }
    }

}

object Mu {

  def in[F[_] : Functor](s: F[Mu[F]]): Mu[F] =
    new Mu[F] {
      def fold[X](k: F[X] => X) = k(s map { _ fold k })
    }

  def out[F[_] : Functor](muF: Mu[F]): F[Mu[F]] =
    muF.fold[F[Mu[F]]] { _ map { s => in(s) } }

}


trait Nu[F[_]] {

  type A

  val a: A

  def unfold(_a: A): F[A]

  def toMu(implicit ev: Functor[F]): Mu[F] =
    new Mu[F] {
      def fold[X](k: F[X] => X) = {
        def go(_a: A): X = k(unfold(a) map go)
        go(a)
      }
    }

}

object Nu {

  def in[F[_] : Functor](s: F[Nu[F]]): Nu[F] =
    new Nu[F] {
      type A = F[Nu[F]]
      val a = s
      def unfold(__a: A) = __a map { nuF => out(nuF) }
    }

  def out[F[_] : Functor](nuF: Nu[F]): F[Nu[F]] =
    nuF unfold nuF.a map { _a =>
      new Nu[F] {
        type A = nuF.A
        val a = _a
        def unfold(__a: A) = nuF unfold (__a)
      }
    }

}


sealed abstract class NatF[X]
final case class Zero[X]() extends NatF[X]
final case class Succ[X](x: X) extends NatF[X]

object NatF {
  implicit val functor: Functor[NatF] =
    new Functor[NatF] {
      def map[A, B](na: NatF[A])(f: A => B) =
        na match {
          case Zero() => Zero()
          case Succ(x) => Succ(f(x))
        }
    }
}


final case class Nat(repr: Mu[NatF]) extends AnyVal {

  def toInt: Int =
    repr.fold[Int] {
      case Zero() => 0
      case Succ(x) => 1 + x
    }

  def succ = Nat succ this

}

object Nat {
  def zero: Nat = Nat(Mu in Zero())
  def succ(n: Nat) = Nat(Mu in Succ(n.repr))
}


sealed abstract class StackF[A, X]
final case class Empty[A, X]() extends StackF[A, X]
final case class Push[A, X](a: A, x: X) extends StackF[A, X]

object StackF {
  implicit def functor[X]: Functor[StackF[X, ?]] =
    new Functor[StackF[X, ?]] {
      def map[A, B](s: StackF[X, A])(f: A => B) =
        s match {
          case Empty() => Empty()
          case Push(x, a) => Push(x, f(a))
        }
    }
}


final case class Stack[A](repr: Mu[StackF[A, ?]]) extends AnyVal {

  def toList: List[A] =
    repr.fold[List[A]] {
      case Empty() => Nil
      case Push(a, x) => a :: x
    }

  def ::(a: A): Stack[A] = Stack.push(a, this)

}

object Stack {
  def empty[A]: Stack[A] = Stack(Mu.in[StackF[A, ?]](Empty()))
  def push[A](h: A, t: Stack[A]) = Stack(Mu.in[StackF[A, ?]](Push(h, t.repr)))
}


final case class Signal[A](repr: Nu[StackF[A, ?]]) extends AnyVal {

  def toStream: Stream[A] = {
    def go(step: StackF[A, repr.A]): Stream[A] =
      step match {
        case Empty() => Stream.empty
        case Push(h, t) => h #:: go(repr.unfold(t))
      }
    go(repr.unfold(repr.a))
  }

}


object Signal {

  def forever[A](a: A)(step: A => A): Signal[A] = {
    type AA = A
    val aa = a
    Signal(
      new Nu[StackF[A, ?]] {
        type A = AA
        val a = aa
        def unfold(_a: A) = Push(_a, step(_a))
      }
    )
  }

  def empty[A]: Signal[A] = Signal(Nu.in[StackF[A, ?]](Empty()))

  def push[A](h: A, t: Signal[A]) = Signal(Nu.in[StackF[A, ?]](Push(h, t.repr)))

}


object RecursionSchemeExample extends App {

  val three: Nat = Nat.zero.succ.succ.succ
  println(three.toInt)

  val stack: Stack[Int] = 1 :: 2 :: 3 :: Stack.empty
  println(stack.toList)

  val signal: Signal[Int] = Signal.forever(0) { _ + 1 }
  println(signal.toStream.take(5).toList)

}