-- -- 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',((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"])) []