Undecidable.scala

sealed trait Undecidable[Nothing, +A]
case object Forever extends Undecidable[Nothing, Nothing]
case class Halt[+A](value: A) extends Undecidable[Nothing, A]

object Undecidable {

  def >==>[A, B, C](
      a: A => Undecidable[Nothing, B],
      b: B => Undecidable[Nothing, C]): A => Undecidable[Nothing, C] = {
    input: A =>
      val unecidableB: Undecidable[Nothing, B] = a(input)
      flatMap(unecidableB)(b)
  }

  def map[A, B](u: Undecidable[Nothing, A])(
      f: A => B): Undecidable[Nothing, B] = {
    u match {
      case forever @ Forever => map(forever)(f)
      case Halt(h)           => Halt(f(h))
    }
  }

  def flatMap[A, B](a: Undecidable[Nothing, A])(
      f: A => Undecidable[Nothing, B]): Undecidable[Nothing, B] = a match {
    case forever @ Forever => flatMap(forever)(f)
    case Halt(h)           => f(h)
  }
  def pure[A](a: A): Undecidable[Nothing, A] = Halt(a)
}