[wrap type Subst in a newtype
Helmut Grohne <grohne@cs.uni-bonn.de>**20140725144508
 Ignore-this: ef00cc96cc607906fbb5042938ae1268
] hunk ./src/Igor2/RuleDevelopment/ListCata.hs 192
-    
-    let v = foldl replaceInverseIn (rhs vr) (filter (hasVars . snd) subs)  
+
+    let v = foldl replaceInverseIn (rhs vr) (filter (hasVars . snd) (assocs subs))
hunk ./src/Igor2/RuleDevelopment/Matching.hs 123
-     let subs' = map (\(n,t) -> (toVar t n,t)) subs
+     let subs' = map (\(n,t) -> (toVar t n,t)) (assocs subs)
hunk ./src/Igor2/RuleDevelopment/Matching.hs 239
-                (Just s) -> do let cllvars = (nub $ concatMap getVars (lhs.crul $ cll))
-                               let bthvars = (nub $ getVars (rhs.crul $ cll)) `intersect` (nub $ getVars (rhs.crul $ tgt))
-                               let unaffectedvars = (cllvars \\ bthvars) \\ (map (\(n,t) -> toVar t n) s)
-                               let s' = s ++ [ (n , (TWildE n t)) | v@(TVarE n t) <- unaffectedvars]
-                               -- replace all vars not in the substitution 
+                Just s   -> do let cllvars = nub $ concatMap getVars (lhs.crul $ cll)
+                               let bthvars = nub (getVars (rhs.crul $ cll)) `intersect` nub (getVars (rhs.crul $ tgt))
+                               let unaffectedvars = (cllvars \\ bthvars) \\ map (\(n,t) -> toVar t n) (assocs s)
+                               -- TODO: the following line may be slow, because merge is linear already
+                               let Just s' = foldM merge nullSubst (s : [ n <~ TWildE n t | TVarE n t <- unaffectedvars])
+                               -- replace all vars not in the substitution
hunk ./src/Syntax/Class/Subst.hs 16
-    
+    lookupS, assocs,
hunk ./src/Syntax/Class/Subst.hs 35
-type Subst t = [(Name,t)]
+newtype Subst t = Subst { assocs :: [(Name,t)] } deriving (Show)
hunk ./src/Syntax/Class/Subst.hs 38
-nullSubst  :: (Substitutable t) => (Subst t)
-nullSubst   = []
+nullSubst  :: (Substitutable t) => Subst t
+nullSubst   = Subst []
hunk ./src/Syntax/Class/Subst.hs 41
--- | Constructing a substitution from a single replacement 
-(<~)      :: (Substitutable t) => Name -> t -> (Subst t)
-n <~ t     = [(n, t)]
+-- | Constructing a substitution from a single replacement
+(<~)      :: (Substitutable t) => Name -> t -> Subst t
+n <~ t     = Subst [(n, t)]
hunk ./src/Syntax/Class/Subst.hs 49
-(@@)       :: (Substitutable t) => (Subst t) -> (Subst t) -> (Subst t)
-s1 @@ s2    = [ (n, apply s1 t) | (n,t) <- s2 ] ++ s1
+(@@)       :: (Substitutable t) => Subst t -> Subst t -> Subst t
+s1 @@ s2    = Subst $ [ (n, apply s1 t) | (n,t) <- assocs s2 ] ++ assocs s1
hunk ./src/Syntax/Class/Subst.hs 56
-merge      :: (Substitutable t,Monad m) => (Subst t) -> (Subst t) -> m (Subst t)
-merge s1 s2 = if agree then return (s1++s2) else fail "merge fails"
-    where 
+merge      :: (Substitutable t, Monad m) => Subst t -> Subst t -> m (Subst t)
+merge s1 s2 = if agree then return $ Subst (assocs s1 ++ assocs s2) else fail "merge fails"
+    where
hunk ./src/Syntax/Class/Subst.hs 60
-                   (on intersect (map fst) s1 s2)
-    var = toVar . snd . head $ s1 
- 
+                   (on intersect (map fst . assocs) s1 s2)
+    var = toVar . snd . head . assocs $ s1
+
+lookupS n (Subst s) = lookup n s
+
hunk ./src/Syntax/Expressions.hs 33
-import Data.Maybe(maybeToList)
+import Data.Maybe (fromMaybe)
hunk ./src/Syntax/Expressions.hs 167
-    apply u v@(TVarE n _) = maybe v id (lookup n u)
+    apply u v@(TVarE n _) = fromMaybe v (lookupS n u)
hunk ./src/Syntax/Type.hs 45
+import Data.Maybe (fromMaybe)
hunk ./src/Syntax/Type.hs 235
-  apply s (VarT u)        = case lookup u s of
-                             Just t  -> t
-                             Nothing -> VarT u
-  apply s (AppT l r)      = appT (apply s l) (apply s r)  
+  apply s (VarT u)        = fromMaybe (VarT u) (lookupS u s)
+  apply s (AppT l r)      = appT (apply s l) (apply s r)
hunk ./src/Syntax/UnifyTy.hs 85
-check s c = reduce c >>= \c' -> allM (checkit c') s >>= failIfFalse  -- . (ts $ "CHECK :\n" ++ (show s) ++ " in " ++ (show c'))
+check s c = do c' <- reduce c
+               allM (checkit c') (assocs s) >>= failIfFalse  -- . (ts $ "CHECK :\n" ++ (show s) ++ " in " ++ (show c'))
