data FOExpr = FONum Int
            | FOVar String
            | FOPlus FOExpr FOExpr
            | FOTimes FOExpr FOExpr
            | FOLetBnd String FOExpr FOExpr
  deriving (Show)

data HOExpr = HONum Int
            | HOPlus HOExpr HOExpr
            | HOTimes HOExpr HOExpr
            | HOLetBnd HOExpr (HOExpr -> HOExpr)
            | HOVar String -- Only used during transformation

foToHO :: FOExpr -> HOExpr
foToHO = foToHO' []
foToHO':: [(String,HOExpr)] -> FOExpr -> HOExpr
foToHO' vars (FONum i) = HONum i
foToHO' vars (FOVar v) = case lookup v vars of
                           Just x -> x
                           Nothing -> undefined
foToHO' vars (FOPlus e1 e2) = HOPlus (foToHO' vars e1) (foToHO' vars e2)
foToHO' vars (FOTimes e1 e2) = HOTimes (foToHO' vars e1) (foToHO' vars e2)
foToHO' vars (FOLetBnd s e1 e2) = HOLetBnd (foToHO' vars e1) (\x->foToHO' ((s,x):vars) e2)

hoToFO = hoToFO' 0
hoToFO' :: Int -> HOExpr -> FOExpr
hoToFO' n (HONum i) = FONum i
hoToFO' n (HOPlus e1 e2) = FOPlus (hoToFO' n e1) (hoToFO' n e2)
hoToFO' n (HOTimes e1 e2) = FOTimes (hoToFO' n e1) (hoToFO' n e2)
hoToFO' n (HOLetBnd e1 e2) = FOLetBnd (show n) (hoToFO' (n+1) e1) (hoToFo' (n+1) $ e2 (HOVar (show n)))
hoToFO' n (HOVar s) = FOVar s