使用foldr在SML中快速排序

Question

我正在做一项额外的作业，其中 SML 中的快速排序的分区函数只能使用 foldr 完成，并且不能使用任何库函数。我已经很好地进行了分区，并且掌握了快速排序的基础知识，但是遇到了问题，似乎将错误的列表合并在一起/以错误的顺序合并。

(*comp is a placeholder, I will be given a comparator function and list as input*)
fun comp a b = a > b;

(*Both partition functions are working as intended.*)
fun getGreater (a::b) c = foldr (fn (a, lst) => if (comp a c) then a::lst else lst) [] (a::b);
fun getLesserOrEqual (a::b) c = foldr (fn (a, lst) => if not (comp a c) then a::lst else lst) [] (a::b);

fun merge (a::b) (c::d) = foldr (op::) (c::d) (a::b);

fun tripleMerge (a::b) c (d::e) = merge (a::b) (c::(d::e));

(*Removes head, uses head as pivot. Recursive calls on results on getLesserOrEqual and getGreater*)
fun sort [] = [] | sort (a::b) = if ([a] = (a::b)) then [a] else
    tripleMerge (sort(getLesserOrEqual b a)) a (sort(getGreater b a));

作为示例，以下是我正在运行的一些测试。当我遵循纸上逻辑时，我没有得到与错误项目相同的答案:

sort [2, 6, 3, 6, 4, 100, 0];
val it = [0,2,3,6,4,6,100] : int list (*Incorrect*)

sort [1, 2, 3, 4, 5];
val it = [1,2,3,4,5] : int list

sort [5, 4, 3, 2, 1];
val it = [5,4,3,2,1] : int list (*incorrect*)

sort [1, 100, 10, 1000, 0];
val it = [0,1,10,100,1000] : int list

sort [1, 2, 1, 2, 1, 2, 5, 1];
val it = [1,1,1,1,2,2,2,5] : int list

我的错误对任何人来说都是显而易见的吗？

Answer 1

以下是一些反馈:

1. This isn't Quicksort .

2. 您可以引用 op > (a, b) (即，将一个运算符变成一个需要一对的函数。

   据我所知，您的实际比较函数是作为输入给出的。一个令人困惑的小点可能是，在标准库中，名为 compare 的函数返回 order 类型，即 LESS、EQUAL 或 GREATER，而不是 bool。但没关系。

3. 正如 John 所说，当函数针对空列表定义良好时，没有真正理由使用模式 a::b。

4. 在函数名称前加上 get 有点多余，因为所有(纯)函数都将某物作为其主要目的。

5. 您可以通过制作更高阶的变体来组合两个过滤函数:

   fun flip f x y = f y x
   fun filter p xs = foldr (fn (x, ys) => if p x then x::ys else ys) [] xs
   fun greaterThan x xs = filter (flip comp x) xs
   fun lessThanOrEqual x xs = filter (comp x) xs
   

6. 似乎 sort 有两种基本情况，一种使用模式处理，另一种使用 if-then-else 处理。为什么？

   fun sort [] = []
     | sort [x] = [x]
     | sort (x::xs) = sort (lessThanOrEqual x xs) @ x :: sort (greaterThan x xs)
   

   或者，如果出于某种原因，您想要最后列出的基本案例:

   fun sort (x::(xs as (_::_))) = sort (lessThanOrEqual x xs) @
                                  x :: sort (greaterThan x xs)
     | sort xs = xs
   

7. 尽管this isn't Quicksort ，所以效率还差得远，你可以做的一件事是改进它，就是只通过 xs 一次，而不是两次。由于我们只被允许foldr，所以我们必须生成一对列表:

   fun partition p xs = foldr (fn (x, (ys, zs)) =>
       if p x then (x::ys, zs) else (ys, x::zs)) ([], []) xs
   
   fun sort [] = []
     | sort [x] = [x]
     | sort (x::xs) =
       let val (lesser, greater) = partition (comp x) xs
       in sort lesser @ x :: sort greater end