SOSML中Union与Quicksort函数实现报错及代码求助

1. Union函数：未定义member的问题 #

报错核心原因是SOSML没有内置member函数，你的代码直接调用了未定义的标识符，导致编译失败。我们可以用模式匹配实现一个判断元素是否在列表中的辅助函数，修正后的代码如下：

(* 辅助函数：用模式匹配判断元素是否存在于列表 *)
fun member (_, []) = false
  | member (x, y::ys) = x = y orelse member (x, ys);

(* 修正后的union函数 *)
fun union ([], ys) = ys
  | union (x::xs, ys) = 
      if member (x, ys) 
      then union (xs, ys) 
      else x :: union (xs, ys);

(* 测试用例 *)
val test_union = union ([3, 4, 7, 9, 8, 5], [5, 7, 6, 2, 1, 8, 9]);
(* 输出包含两列表所有无重复元素的列表，顺序不限 *)

如果不想单独定义member，也可以把判断逻辑内嵌到union的模式匹配中：

fun union ([], ys) = ys
  | union (x::xs, ys) =
      let
        fun is_present [] = false
          | is_present (y::ys) = x = y orelse is_present ys
      in
        if is_present ys then union (xs, ys) else x :: union (xs, ys)
      end;

2. Quicksort函数：类型错误与超时问题 #

错误根源 #

• 类型错误：原partition函数逻辑混乱，返回的元组类型与后续赋值不匹配，导致ML类型推导出错，出现int list → 'b list的错误类型。
• 超时（无限递归）：原partition函数错误地遍历初始为空的less参数，而非待分区的xs列表，导致无法处理输入元素，最终让quicksort陷入无限递归。

修正后的代码 #

重新设计partition函数，用模式匹配遍历待分区列表，正确拆分出小于、等于、大于基准值的子列表：

fun quicksort [] = []
  | quicksort (x::xs) =
      let
        (* 模式匹配实现分区：返回(小于基准的列表, 等于基准的列表, 大于基准的列表) *)
        fun partition (pivot, [], less, equal, greater) = (less, equal, greater)
          | partition (pivot, y::ys, less, equal, greater) =
              if y < pivot 
              then partition (pivot, ys, y::less, equal, greater)
              else if y = pivot 
              then partition (pivot, ys, less, y::equal, greater)
              else partition (pivot, ys, less, equal, y::greater);

        val (less, equal, greater) = partition (x, xs, [], [x], [])
      in
        quicksort less @ equal @ quicksort greater
      end;

(* 测试用例 *)
val test_quicksort = quicksort [3, 4, 7, 9, 8, 5, 6, 2];  
(* 输出：[2, 3, 4, 5, 6, 7, 8, 9] *)

关键修正点 #

• 调整partition参数，让它真正遍历待分区的xs列表；
• 分区函数返回三个子列表，确保基准值不会丢失，同时减少冗余递归；
• 结果拼接时加入equal列表，保证排序结果完整。

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