SimpleGeneralizedZipper.scala

object SimpleGeneralizedZipper {

  sealed abstract class Direction
  final case object Haut    extends Direction
  final case object Gauche  extends Direction
  final case object Droite  extends Direction

  sealed abstract class Stream[-I, +A] {
    def focus : A
    def cont : I => Stream[I, A]
  }
  final case class  Cons[-I, +A](focus : A, cont : I => Stream[I, A]) extends Stream[I, A]
  final case object End                                               extends Stream[Any, Nothing] {
    def focus: Nothing = ???
    def cont: Any => Stream[Any, Nothing] = ???
  }

  // (A => T) => T

  trait CPS[I, X, A] { self =>
    def apply(k : A => Stream[I, X]) : Stream[I, X]

    def map[B](f : A => B) = new CPS[I, X,B] {
      def apply(k: B => Stream[I, X]): Stream[I, X] = self.apply((a:A) => k(f(a)))
    }

    def flatMap[B](f : A => CPS[I, X,B]) = new CPS[I, X,B] {
      def apply(k: B => Stream[I, X]): Stream[I, X] = self.apply((a:A) => f(a).apply(k))
    }

    def run : Stream[I, X] = self.apply(_ => End)
  }

  object CPS {

    def pure[I,X,A](a : A) = new CPS[I, X,A] {
      def apply(k: A => Stream[I, X]): Stream[I, X] = k(a)
    }
    def apply[I,X,A](f : (A => Stream[I, X]) => Stream[I, X]) = new CPS[I, X,A] {
      def apply(k: (A) => Stream[I, X]): Stream[I, X] = f(k)
    }
  }

  def pause[I, X](focus : X) = new CPS[I, X, I] {
    def apply(k: I => Stream[I, X]): Stream[I, X] = Cons(focus, k)
  }

  sealed abstract class Tree[+A]
  final case object Vide                                         extends Tree[Nothing]
  final case class  Leaf[+A](value : A)                          extends Tree[A]
  final case class  Node[+A](gauche : Tree[A], droite : Tree[A]) extends Tree[A]

  def parcourir[A](t : Tree[A]) : CPS[Either[Tree[A] , Direction], Tree[A], Tree[A]] = {

    def aux(t2 : Tree[A]) : CPS[Either[Tree[A] , Direction], Tree[A], Tree[A]] =
      pause(t2).flatMap {
        case Left(nt) =>
            aux(nt)

        case Right(d) => (d, t2) match {
          case (Haut  , _) =>
            CPS.pure(t2)

          case (Gauche, Node(g,d)) =>
            aux(g).flatMap(ng => aux(Node(ng,d)))

          case (Droite, Node(g,d)) =>
            aux(d).flatMap(nd => aux(Node(g,nd)))

          case _ =>
            aux(t2)
      }
    }

    aux(t)
  }

  def d[A](dir : Direction) : Either[Tree[A], Direction] = Right(dir)
  def t[A](tree : Tree[A]) : Either[Tree[A], Direction] = Left(tree)

  val cps = parcourir(Node(Node(Leaf(1), Vide), Node(Leaf(2), Leaf(3))))



}