package object recs {

//Recursive Functions

abstract class Rec {
  def eval(ns: List[Int]) : Int
}

case object Z extends Rec {
  override def eval(ns: List[Int]) = ns match {
    case n::Nil => 0
    case _ => throw new IllegalArgumentException("Z: args")
  }
} 

case object S extends Rec {
  override def eval(ns: List[Int]) = ns match {
    case n::Nil => n + 1
    case _ => throw new IllegalArgumentException("S: args")
  }
} 

case class Id(n: Int, m: Int) extends Rec {
  override def eval(ns: List[Int]) = 
    if (ns.length == n && m < n) ns(m)
    else throw new IllegalArgumentException("Id: args")
}

case class Cn(n: Int, f: Rec, gs: List[Rec]) extends Rec {
  override def eval(ns: List[Int]) = 
    if (ns.length == n) f.eval(gs.map(_.eval(ns)))
    else throw new IllegalArgumentException("Cn: args")
}

case class Pr(n: Int, f: Rec, g: Rec) extends Rec {
  override def eval(ns: List[Int]) = 
    if (ns.length == n + 1) {
      if (ns.last == 0) f.eval(ns.init)
      else {
        val r = Pr(n, f, g).eval(ns.init ::: List(ns.last - 1))
        g.eval(ns.init ::: List(ns.last - 1, r))
      }
    }
    else throw new IllegalArgumentException("Pr: args")
}

case class Mn(n: Int, f: Rec) extends Rec {
  def evaln(ns: List[Int], n: Int) : Int = 
    if (f.eval(ns ::: List(n)) == 0) n else evaln(ns, n + 1)

  override def eval(ns: List[Int]) = 
    if (ns.length == n) evaln(ns, 0) 
    else throw new IllegalArgumentException("Mn: args")
}

}