The essence of Lazy Z compiler

gistfile1.hs

data ExprP = Var String | Apply ExprP ExprP | Lambda String ExprP -- lambda calculus expression

data Expr = I | K | S | Expr :$ Expr | Free String -- combinatory expression

compile :: ExprP -> Expr
compile (Apply f x) = compile f :$ compile x
compile (Lambda p e) = bindee p $ compile e
compile (Var i) = Free i

bindee :: String -> Expr -> Expr
bindee p (Free p') | p == p' = I
bindee p (f :$ g) = S :$ bindee p f :$ bindee p g
bindee _ e = K :$ e