SML实现AVL树左旋转函数遇匹配非穷尽警告如何修复？

你遇到的这个警告是因为你的rotate_left函数没有覆盖AVLTree所有可能的结构。咱们先拆解一下问题：

你的原函数只处理了两种情况：Nil，以及右子树是Br节点的Br节点。但Br节点的右子树还可能是Nil，这种情况你的函数完全没匹配到，所以SML解释器会提示匹配非穷尽。

修复方案 #

你可以通过补充未覆盖的模式来解决这个问题，有两种常见的思路：

1. 显式处理右子树为空的情况

这种方式更清晰，明确告诉编译器当右子树是Nil时不需要旋转，直接返回原节点：

fun rotate_left Nil = Nil
  | rotate_left (Br(x, A, Nil)) = Br(x, A, Nil)  (* 右子树为空，无需执行左旋转 *)
  | rotate_left (Br(x, A, Br(y, B, C))) = Br(y, Br(x, A, B), C);

2. 用通配符兜底所有剩余情况

如果你不想逐个枚举剩余的结构，可以在最后加一个通配符模式，覆盖所有不满足左旋转条件的树结构（本质上就是直接返回原树，因为这些情况不需要旋转）：

fun rotate_left Nil = Nil
  | rotate_left (Br(x, A, Br(y, B, C))) = Br(y, Br(x, A, B), C)
  | rotate_left tree = tree;  (* 兜底所有其他情况 *)

为什么你之前用通配符没成功？ #

大概率是通配符的位置放错了！SML的模式匹配是从上到下依次匹配的，你必须把具体的、有特殊逻辑的模式放在前面，通配符这种兜底模式放在最后。如果把通配符放在前面，后面的具体模式永远不会被匹配到，反而会引发新的问题。

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