SML 数据类型匹配冗余产生冗余

Question

我从 The Little MLer

那里得到了这个

datatype 'a pizza =
         Bottom
         | Topping of ('a * ('a pizza))

还有这个

datatype fish =
         Anchovy
         | Lox
       | Tuna

和这个工作代码

fun rem_fish (f, fp) =
    let
        fun eq_fish (Anchovy,Anchovy) = true
          | eq_fish (Lox,Lox) = true
          | eq_fish (Tuna,Tuna) = true
          | eq_fish (_,_) = false
    in
        case fp of
            Bottom => Bottom
          | Topping(x,y) =>
            case eq_fish (f,x) of
                true => rem_fish (f,y)
              | false => Topping (x,rem_fish (f,y))
end

这将采用鱼类型和鱼披萨对，并在第一个参数中删除该特定鱼

- rem_fish (Tuna, Topping (Tuna, (Topping (Anchovy, Topping (Lox, Topping (Tuna, Bottom))))));
Topping (Anchovy,Topping (Lox,Bottom)) : fish pizza

很好，然后我看到这段代码（我已将其更改为基于 case）标记为 "ungrammatical"

fun rem_fish (f, fp) =
        case fp of
            Bottom => Bottom
          | Topping (f,fp') => rem_fish (f,fp')
          | Topping (x,fp') => Topping (x,rem_fish (f,fp'))

但是这个错误

Error: match redundant
:           Bottom => ...
:           Topping (f,fp') => ...
:     -->   Topping (x,fp') => ...

这个错误是什么意思？代码有什么问题？最后一行可能是这样的

Topping (_,fp') => Topping (?,rem_fish (f,fp'))

但后来我不知道 ? 可能是什么。

Answer 1

我认为如果我们消除这段代码中一些不需要的阴影，它可能会变得更清晰。考虑函数

fun rem_fish (f, fp) =
        case fp of
            Bottom => Bottom
          | Topping (y,fp') => rem_fish (y,fp')
          | Topping (x,fp') => Topping (x,rem_fish (f,fp'))

这相当于你写的。

请注意，Topping (y,fp') 和 Topping (x,fp') 都是 Topping 变体的无可辩驳的模式；他们总是会匹配它。所以在你的代码中，如果你有一个 Topping 它将始终匹配你的 case 的第二个分支，因此第三个分支是多余的（错误在说什么）。

如果您希望能够检查由 Topping 包裹的元组中的第一个元素是否等于 f，您需要使用 [=19= 明确地这样做] （强制它是一个相等类型），或者将某种相等函数作为参数来检查（或者像在初始示例中那样在内部使用它）。后者可能看起来像

fun rem_fish (_, Bottom) _ = Bottom
  | rem_fish (f, Topping (x, fp)) cmp = 
      if cmp (f, x) then
        rem_fish (f, fp)
      else
        Topping (x, rem_fish (f, fp))

（对于除具有相等功能的鱼以外的浇头，它可以更通用一些）

SML 数据类型匹配冗余产生冗余

SML datatype match redundant produces redundancy

types

sml