cantor.scala

// http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/

package codes.quine.labo

package object cantor {
  type Bit = Boolean

  val Zero = false
  val One = true

  type Cantor = LazyList[Bit]

  def find(p: LazyList[Bit] => Boolean): LazyList[Bit] = {
    lazy val bit = if (p(LazyList.cons(Zero, find(bits => p(LazyList.cons(Zero, bits)))))) Zero else One
    LazyList.cons(bit, find(bits => p(LazyList.cons(bit, bits))))
  }

  def exists(p: Cantor => Boolean): Boolean = p(find(c => p(c)))
  def forall(p: Cantor => Boolean): Boolean = !exists(c => !p(c))

  def equal[A](f: Cantor => A, g: Cantor => A): Boolean = forall { c => f(c) == g(c) }

  def coerce(bit: Bit): Int = if (bit == Zero) 0 else 1

  def f(c: Cantor): Int = coerce(c(7 * coerce(c(4)) + 4 * coerce(c(7)) + 4))

  def g(c: Cantor): Int = coerce(c(coerce(c(4)) + 11 * coerce(c(7))))

  def h(c: Cantor): Int =
    if (c(7) == Zero)
      if (c(4) == Zero) coerce(c(4)) else coerce(c(11))
    else if (c(4) == One) coerce(c(15)) else coerce(c(8))
}