queue.scala

import scala.annotation.tailrec
import scala.language.higherKinds

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, g :+ f)
    }
}
case class Pure[F[_], A](a: A) extends Freer[F, A]
case class Impure[F[_], A, B](fa: F[A], f: Queue[F, A, B]) extends Freer[F, B]

sealed abstract class Queue[U[_], A, B] {

  def apply(a: A): Freer[U, B] = {
    @tailrec
    def go(tpe: { type T })(arrows: Queue[U, tpe.T, B], value: tpe.T): Freer[U, B] =
      arrows.view match {
        case One(f) => f(value)
        case cons@Cons() =>
          cons.head(value) match {
            case Pure(value) => go(new { type T = cons.T })(cons.tail, value)
            case Impure(fa, f) => Impure(fa, f ++ cons.tail)
          }
      }
    go(new { type T = A })(this, a)
  }

  def :+[C](f: B => Freer[U, C]): Queue[U, A, C] = Node(this, Leaf(f))

  def ++[C](that: Queue[U, B, C]): Queue[U, A, C] = Node(this, that)

  def view: View[U, A, B]

}

case class Leaf[U[_], A, B](arrow: A => Freer[U, B]) extends Queue[U, A, B] {

  lazy val view: View[U, A, B] = One(arrow)

}

sealed abstract case class Node[U[_], A, B]() extends Queue[U, A, B] { self =>

  type T

  def left: Queue[U, A, T]

  def right: Queue[U, T, B]

  lazy val view: View[U, A, B] = {
    @tailrec
    def go[U[_], A, B](tpe: { type T })(left: Queue[U, A, tpe.T], right: Queue[U, tpe.T, B]): View[U, A, B] =
      left match {
        case Leaf(value) => Cons(value, right)
        case node@Node() => go[U, A, B](new { type T = node.T })(node.left, Node(node.right, right))
      }
    go(new { type T = self.T })(left, right)
  }

}

object Node {

  def apply[U[_], A, B, C](f: Queue[U, A, B], g: Queue[U, B, C]): Node[U, A, C] =
    new Node[U, A, C] {
      type T = B
      val left: Queue[U, A, B] = f
      val right: Queue[U, B, C] = g
    }

}

sealed abstract class View[U[_], -A, +B]

case class One[U[_], A, B](arrow: A => Freer[U, B]) extends View[U, A, B]

sealed abstract case class Cons[U[_], A, B]() extends View[U, A, B] {

  type T

  def head: A => Freer[U, T]

  def tail: Queue[U, T, B]

}

object Cons {

  def apply[U[_], A, B, C](h: A => Freer[U, B], t: Queue[U, B, C]): Cons[U, A, C] =
    new Cons[U, A, C] {
      type T = B
      val head: A => Freer[U, B] = h
      val tail: Queue[U, B, C] = t
    }

}