import Data.List

type Variable = String

data Expr = Var Variable
          | Lambda Variable Expr
          | Ap Expr Expr
            deriving (Show, Read, Eq, Ord)

-- De Bruijn indexing
data DExpr = DVar Int
           | DLambda DExpr
           | DAp DExpr DExpr
             deriving (Show, Read, Eq, Ord)

-- What is a more idiomatic way to do this?
toDeBruijn_ :: [String] -> Expr -> DExpr
toDeBruijn_ vars (Var v) = maybe (
                            error $ "Unexpected free variable `" ++ v ++ "`"
                          ) DVar $ findIndex (== v) vars
toDeBrujin_ vars (Lambda v e) = toDeBrujin_ (v:vars) e
toDeBrujin_ vars (Ap f x) = DAp (toDeBrujin_ vars f) (toDeBrujin_ vars x)
toDeBrujin_ vars a = error ("Unexpected `" ++ show a ++ "`")

toDeBrujin :: Expr -> DExpr
toDeBrujin = toDeBrujin_ []