--
-- Setting up the state monad
--
data SM s a = Sm (s -> (a,s))

runSM:: (SM s a) -> (s -> (a,s))
runSM (Sm h) = h

instance Monad (SM s) where
     return y = Sm (\s -> (y,s))
     (Sm f) >>= g = Sm (\s -> (\(y,s') -> runSM (g y) s') (f s)) where
                
--
-- Substituting the variables of an expression with (new) numbers
--
data Exp a b = Var b
             | Opn a [Exp a b]
     deriving (Eq,Show)

type Substs = [(String,Int)]

--
--  the substitution of a string either replaces the string with a number as specified in 
--  the list of substitutions or adds a substitution using the lest number available ...
--
subst:: String -> (SM Substs Int)
subst str = 
   Sm (\subs -> case (insubs str subs) of
                   Just n -> (n,subs)
                   Nothing ->(next_free str 0 subs))  where
         insubs str [] = Nothing
         insubs str ((str',n):subs)| str==str' = Just n
                                   | otherwise = insubs str subs
         next_free str n [] = (n,[(str,n)])
         next_free str n ((str',m):subs)
                    | n<m = (n,(str,n):((str',m):subs))
                    | otherwise = (\(m',subs') -> (m',((str',m):subs')))
                                  (next_free str (n+1) subs)

--                   
--  The code for substitution of an expression using the state monad ...
--
subst_exp (Var x) = do n <- subst x
                       return (Var n)
subst_exp (Opn f ts) = do ts' <- subst_list ts
                          return (Opn f ts')  where
         subst_list [] = return []
         subst_list (t:ts) = do t' <- subst_exp t
                                ts' <- subst_list ts
                                return (t':ts')

ans = runSM (subst_exp (Opn "f" [Var "a",Var "b",Var"a"])) []