SML datatype match redundant produces redundancy

I have this from The Little MLer

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

and this

datatype fish =
         Anchovy
         | Lox
       | Tuna

and this working code

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

which will take a fish type and a fish pizza pair and remove that particular fish in the first argument

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

Good, so I then see this code (which I've changed to be case based) marked as "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'))

but this error

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

What does this error mean? What's wrong with the code? The last line could have been something like this

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

but then I don't know what ? could have been.

Solution

I think it may become clearer if we eliminate some unneeded shadowing in this code. Consider the function

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

which is equivalent to what you've written.

Notice that both Topping (y,fp') and Topping (x,fp') are irrefutable patterns for a Topping variant; they'll always match it. So in your code, if you have a Topping it will match the second branch of your case always, and thus the third branch is redundant (what the error is saying).

If you want to be able to check if the first element in the tuple wrapped by Topping is equal to f, you'll either need to explicitly do so with op= (forcing it to be an equality type), or take some sort of equality function as a parameter to check with (or have it internally as you do in the initial example). The latter might look something like

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

(which can then be a bit more general for toppings other than fish that have equality functions)