(SIG 
   (app   List List -> List)
   (cons  Nat List -> List)
   (nil   -> List)
   (s     Nat -> Nat)
   (0     -> Nat)
 )
 (RULES
   app(nil,ys) -> ys
   app(cons(x,xs),ys) -> cons(x,app(xs,ys))
 )