在case表达式/列表推导中的模式匹配

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')

但是这并不是。

奇怪的是，显式匹配有效：

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
复合型（原子'b'）（原子'c'）

>: subs''' subList term1 或者 >: subs''' subList term2
原子'x'

我错过了什么吗？

- jules

---

为了避免将来陷入这种错误，我建议使用-Wall打开GHC警告：这将指出x被绑定两次（内部的x掩盖了外部的x）。 - chi

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)

- András Kovács

---

非常感谢。如果我理解正确，那么在任何情况下 a 都必须是 Eq 的一个实例？ - jules

@jules 是的。我们在模式匹配中没有相等性测试的一个原因是并非所有类型都是 Eq 的实例。我猜它仍然可以作为语法糖实现，但没有人真正认为这值得麻烦。 - András Kovács