表達式/列表解析中的模式匹配

Question

爲什麼以下嘗試在列表理解中模式匹配不起作用？

示例：同時替換術語數據類型中的原子。

的數據類型：

data Term a 
    = Atom a 
    | Compound (Term a) (Term a) 
    deriving Show 

在術語原子的取代算法（採第一匹配取代如果任何和忽略其餘部分）：

subs :: [(Term a, Term a)] -> Term a -> Term a 
subs subList term = case term of 
    atom@(Atom x)  -> let substitutions = 
           [ s | s@(Atom x, _) <- subList ] 
          in if null substitutions 
           then atom 
           else snd . head $ substitutions 
    (Compound t1 t2) -> Compound (subs subList t1) (subs subList t2) 

一些測試數據：

subList = [((Atom 'a'), Compound (Atom 'b') (Atom 'c'))] 
term1 = Atom 'a' 
term2 = Atom 'x' 

運行示例結果如下：

>: subs subList term1 
Compound (Atom 'b') (Atom 'c') 

這是所期望的行爲，和

>: subs subList term2 
Compound (Atom 'b') (Atom 'c') 

這是不。

Strangley明確的匹配工作的：

subs'' :: [(Term Char, Term Char)] -> Term Char -> Term Char 
subs'' subList term = case term of 
    atom@(Atom _)  -> let substitutions = 
          [ s | s@(Atom 'a', _) <- subList ] 
          in if null substitutions 
           then atom 
           else snd . head $ substitutions 
    (Compound t1 t2) -> Compound (subs subList t1) (subs subList t2) 

subs''' subList term = case term of 
    atom@(Atom _)  -> let substitutions = 
          [ s | s@(Atom 'x', _) <- subList ] 
          in if null substitutions 
           then atom 
           else snd . head $ substitutions 
    (Compound t1 t2) -> Compound (subs subList t1) (subs subList t2) 

進料與所述測試數據導致：

>: subs'' subList term1或>: subs'' subList term2
Compound (Atom 'b') (Atom 'c')

>: subs''' subList term1或>: subs''' subList term2
Atom 'x'

我錯過了什麼？

Answer 1

Haskell具有線性模式，這意味着模式中不能有重複的變量。此外，內部表達式中的模式變量會影響外部變量，而不是建立相同變量的相等性。

你試圖做這樣的事情：

charEq :: Char -> Char -> Bool 
charEq c c = True 
charEq _ _ = False 

但是，這是因爲重複變量的錯誤。假如我們把第二c到內表達，它編譯，但它仍打算不起作用：

charEq :: Char -> Char -> Bool 
charEq c d = case d of 
    c -> True 
    _ -> False 

這裏內c只是一個新的變量，陰影外c，所以charEq總是返回True。

如果我們想檢查平等，我們必須使用==明確：

subs :: [(Term a, Term a)] -> Term a -> Term a 
subs subList term = case term of 
    atom@(Atom x)  -> let substitutions = 
           [ s | s@(Atom x', _) <- subList, x == x' ] 
          in if null substitutions 
           then atom 
           else snd . head $ substitutions 
    (Compound t1 t2) -> Compound (subs subList t1) (subs subList t2)