Abstraction elimination

unabstract.hs

import Control.Applicative
infixl 9 :$

data Expr = Lambda String Expr -- Lambda term
    | Free String -- Free variable
    | S | K | I -- SKI combinator
    | Expr :$ Expr -- Application

-- transformation which converts a lambda term to a SKI combinator
unabstractLambda :: String -- name of the formal parameter
    -> Expr -- body
    -> Expr -- transformed expression

unabstractLambda v (Lambda w e) = unabstractLambda v (unabstractLambda w e)
unabstractLambda x (Free x') | x == x' = I -- λx.x -> I
unabstractLambda x (f :$ g) = S :$ unabstractLambda x f :$ unabstractLambda x g -- λx.f g -> S f g
unabstractLambda _ y = K :$ y -- \x.y (y doesn't depend x) -> K y