冗余模式匹配

Question

我正在尝试编写一个函数来查找给定数字 n 是否为完全平方数。这是我的尝试：

local
  fun perfect_square_iter x z = let val sqr = z * z in
    case (x,z) of
        (sqr,_) => true
      | (_, 0) => false
      | _ => perfect_square_iter x (z - 1)
    end
in fun perfect_square n = perfect_square_iter n n
end

现在，当我尝试使用 sml myfile.sml 运行时，出现以下错误：

lab03.sml:17.5-20.43 Error: match redundant
          (sqr,_) => ...
    -->   (_,0) => ...
    -->   _ => ...

/usr/lib/smlnj/bin/sml: Fatal error -- Uncaught exception Error with 0
 raised at ../compiler/FLINT/trans/translate.sml:1735.13-1735.21

这对我来说似乎不是一个多余的模式，因为它只匹配两个常量，然后匹配其他任何东西。为什么编译器认为这是多余的？

Answer 1

sqr 不是常量，即使您对它进行了 let 绑定。从句法上讲，它是一个变量，在模式语言中，所有变量都是可以匹配任何内容的自由变量。因此，您的模式 (sqr,_) 匹配所有参数。逗号前的值将绑定到该子句正文中的 sqr（=> 的 RHS），从而隐藏您对 z*z 的绑定，它之后的值将是丢弃。这涵盖了所有可能的情况，因此您的其余匹配是多余的。

您可以通过考虑以下（绝对糟糕的）代码来验证模式中的变量匹配是否引入了新的局部作用域：

fun f xs =
    let val x = 5 in
        case xs of
            [] => 0
        |   x::xs => x
    end;

它编译，但是然后，例如 f [1,7,10] returns 1 而不是 5。

对于您的代码，您需要使用 if ... then ... else 而不是模式匹配来处理 x = sqr 的情况。像

(_,0) => false
| (_,_) => if x = sqr ...

（这是假设您仍然想使用模式匹配，但是由于您不能按照您想要的方式使用它，因此可以对代码进行更彻底的重组，例如免除 let 可能合适）。

冗余模式匹配

Redundant Pattern Matching

pattern-matching

sml

ml

perfect-square