A conversion from Lambda Calculus to SK calculus

Bracket.hs

module Bracket where

data Lam = Var Int | Ap Lam Lam | Lam Lam deriving Show
data SK  = S | K | SKAp SK SK deriving Show

data SKH = Var' Int | S' | K' | SKAp' SKH SKH

-- Remove one variable
bracket :: SKH -> SKH
bracket (Var' 0) = SKAp' (SKAp' S' K') K'
bracket (Var' i) = Var' (i - 1)
bracket (SKAp' l r) = SKAp' (SKAp' S' (bracket l)) (bracket r)
bracket x = x

close :: SKH -> SK
close (Var' _) = error "Not closed"
close S' = S
close K' = K
close (SKAp' l r) = SKAp (close l) (close r)

l2h :: Lam -> SKH
l2h (Var i) = Var' i
l2h (Ap l r) = SKAp' (l2h l) (l2h r)
l2h (Lam h) = bracket (l2h h)

translate :: Lam -> SK
translate = close . l2h