Injection.scala

object Injection {
  // A table of constant 0 functions
  def zeroes: Int => (Int => Int) = (n1: Int) => (n2: Int) => 0
  
  // Update an entry in a function table with a new function at the given position.
  def update(t: Int => (Int => Int), k: Int, f: Int => Int): Int => (Int => Int) = {
    (n: Int) => if (n == k) f else t(n)
  }
  
  def diag(hinv: Int => (Int => Int)): Int => Int = {
    (n: Int) => hinv(n)(n) + 1
  }
  
  def invert(H: (Int => Int) => Int): Int => (Int => Int) = {
    @tailrec
    def iter(hinv: Int => (Int => Int)): Int => (Int => Int) = {
      val d = diag(hinv)
      val k = H(d)
      if (H(hinv(k)) == k) {
        // Found a collision!
        hinv
      } else {
        // The function at position k is incorrect, so update it and loop around.
        iter(update(hinv, k, d))
      }
    }
    iter(zeroes)
  }
  
  def solve(H: (Int => Int) => Int): (Int => Int, Int => Int, Int) = {
    val hinv = invert(H)
    val d = diag(hinv)
    val k = H(d)
    val fk = hinv(k)
    (d, fk, k)
  }
  
  def solve2(H: (Int => Int) => Int): (Int => Int, Int => Int, Int) = {
    // The constant 0 function
    def g = (n: Int) => 0
    
    // f(i) is zero everywhere except at i.
    def f(i: Int) = (n: Int) => if (n == i) 1 else 0
  
    @tailrec
    def search(i: Int): Int = {
      if (H(f(i)) == H(g)) i
      else search(i+1)
    }
    val k = search(0)
    (f(k), g, k)
  }
}

object Examples {
  def h1(f: Int => Int): Int = f(1) * 2
  
  def h2(f: Int => Int): Int = f(1) + f(2)
  
  def h3(f: Int => Int): Int = f(1) + f(f(0))
  
  def h4(f: Int => Int): Int = f(1) + 5
  
  def h5(f: Int => Int) = {
    def pow(b: Int, e: Int) = math.pow(b, e).toInt
    pow(2, f(f(0))) + pow(3, f(f(f(1)))) + pow(5, f(2)) + pow(7, f(3))
  }
  
  def h6(f: Int => Int) = {
    def rec(f: Int => Int, x: Int, n: Int): Int = {
      if (n == 0) x else f(rec(f, x, n-1))
    }
    rec((x: Int) => f(x) + 1, f(0), f(1))
  }
  
  def test(H: (Int => Int) => Int) = {
    val (f, g, k) = solve(H)
    println("H(f) = %d".format(H(f)))
    println("H(g) = %d".format(H(g)))
    println("f(k) = %d".format(f(k)))
    println("g(k) = %d".format(g(k)))
    (f, g, k)
  }
  
  def test2(H: (Int => Int) => Int) = {
    val (f, g, k) = solve2(H)
    println("H(f) = %d".format(H(f)))
    println("H(g) = %d".format(H(g)))
    println("f(k) = %d".format(f(k)))
    println("g(k) = %d".format(g(k)))
    (f, g, k)
  }
}