sealed trait SKI
case object S extends SKI
case object K extends SKI
case object I extends SKI
case class APP(x: SKI, y: SKI) extends SKI
case class VAR(v: String) extends SKI


object SKI {

  def eval(x: SKI): SKI = x match {
    case APP(I, x) => eval(x)
    case APP(APP(K, x), y) => eval(x)
    case APP(APP(APP(S, x), y), z) => eval(APP(APP(x, z), APP(y, z)))
    case APP(x, y) => {
      val app = APP(eval(x), eval(y))
      if(APP(x, y) == app) app
      else eval(app)
    }
    case x => x
  }

  def main(args: Array[String]): Unit = {
    println(eval(APP(I, VAR("x"))))
    println(eval(APP(APP(K, APP(I, VAR("x"))), VAR("y"))))
    println(eval(APP(APP(APP(S, I), I), VAR("x"))))
    println(eval(APP(APP(I, I), VAR("x"))))
  }

}