SML列表排序问题求助：非穷举匹配异常

Hey there! Let's break down why your simpSort is hitting that uncaught exception Match error when you call simpSort([3,1]), and fix it up properly.

1. 首先修复remElem函数的模式匹配漏洞 #

你的remElem函数只处理了空列表和至少包含两个元素的列表，但当你尝试从单元素列表（比如从[3,1]移除1后剩下的[3]）中移除元素时，没有对应的匹配分支——这正是触发Match异常的直接原因。

下面是修复后的remElem，它覆盖了所有长度的列表，用递归逻辑干净地处理了所有情况（注意：这个版本只会移除第一个匹配的元素，符合选择排序的需求）：

fun remElem(x, l) = 
    case l of 
        [] => [] 
      | [x1] => if x1 = x then [] else [x1]
      | (x1::xs) => if x1 = x then xs else x1::remElem(x, xs);

2. 修正simpSort中aux函数的逻辑错误 #

在你的aux辅助函数里，[x] => [x]这个分支逻辑有误——它丢弃了已经构建好的有序列表acc，直接返回当前的单个元素。比如排序[3,1]时，当我们把1移到acc后，xs剩下[3]，这个分支会返回[3]而不是正确的[1,3]。

把这个分支修改为将单个元素追加到acc末尾：

fun aux(xs, acc) = 
    case xs of 
        [] => acc 
      | [x] => acc @ [x]
      | _ => let val m = minList(xs) in aux(remElem(m, xs), acc @ [m]) end

3. （可选）优化minList函数 #

你原本的minList能正常工作，但用x作为初始最小值后，再把x::xs传给foldl有点冗余，我们可以简化为只遍历xs：

fun minList(x::xs) = List.foldl (fn (curr, min_val) => if curr < min_val then curr else min_val) x xs;

完整修复后的代码 #

把所有修改整合起来，这就是可以正常运行的版本：

fun minList(x::xs) = List.foldl (fn (curr, min_val) => if curr < min_val then curr else min_val) x xs;

fun remElem(x, l) = 
    case l of 
        [] => [] 
      | [x1] => if x1 = x then [] else [x1]
      | (x1::xs) => if x1 = x then xs else x1::remElem(x, xs);

fun simpSort(xs) = 
    let 
        fun aux(xs, acc) = 
            case xs of 
                [] => acc 
              | [x] => acc @ [x]
              | _ => let val m = minList(xs) in aux(remElem(m, xs), acc @ [m]) end
    in 
        aux(xs, []) 
    end;

现在测试simpSort([3,1])，它会正确返回[1,3]，不会再触发异常。你也可以试试[5,2,7,1]这类列表，确认它能正常完成选择排序。

内容的提问来源于stack exchange，提问作者Sri