使用 foldr 在 SML 中快速排序
Quicksort in SML using foldr
我正在做一项额外的作业,其中 SML 中快速排序的分区函数只能用 foldr
完成,并且不能使用库函数。我已经很好地划分了分区,也很好地掌握了快速排序的基础知识,但是 运行 遇到了似乎以错误顺序合并错误列表 together/merge 的问题。
(*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
我的错误对任何人来说都是显而易见的吗?
我看到的唯一错误是您的 merge
和 tripleMerge
函数。通过使用像 a::b
这样的模式,您将不允许空列表。但是——当基准是最小或最大元素时,您的分区函数之一将返回空列表。如果你像这样调整这两个函数的代码:
fun merge xs ys = folder (op::) ys xs;
fun tripleMerge xs y ys = merge xs (y::ys);
并保留其余代码,它将按预期工作。
这里有一些反馈:
This isn't Quicksort.
你可以参考op >
(a, b)
而不是写fun comp a b = a > b
(即把一个运算符变成一个接受一对的函数)。
我了解到您的实际比较函数是作为输入给出的。一个小的混淆点可能是在标准库中,名为 compare
return 和 order 类型的函数,即 LESS
、EQUAL
或 GREATER
,而不是 bool。不过没关系。
正如 John 所说,当函数为空列表 well-defined 时,没有真正的理由使用模式 a :: b
。
函数名称前缀 get
有点多余,因为所有(纯)函数的主要目的都是 something。
您可以通过制作更高阶的变体来组合您的两个过滤函数:
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
似乎 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
尽管 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
我正在做一项额外的作业,其中 SML 中快速排序的分区函数只能用 foldr
完成,并且不能使用库函数。我已经很好地划分了分区,也很好地掌握了快速排序的基础知识,但是 运行 遇到了似乎以错误顺序合并错误列表 together/merge 的问题。
(*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
我的错误对任何人来说都是显而易见的吗?
我看到的唯一错误是您的 merge
和 tripleMerge
函数。通过使用像 a::b
这样的模式,您将不允许空列表。但是——当基准是最小或最大元素时,您的分区函数之一将返回空列表。如果你像这样调整这两个函数的代码:
fun merge xs ys = folder (op::) ys xs;
fun tripleMerge xs y ys = merge xs (y::ys);
并保留其余代码,它将按预期工作。
这里有一些反馈:
This isn't Quicksort.
你可以参考
op >
(a, b)
而不是写fun comp a b = a > b
(即把一个运算符变成一个接受一对的函数)。我了解到您的实际比较函数是作为输入给出的。一个小的混淆点可能是在标准库中,名为
compare
return 和 order 类型的函数,即LESS
、EQUAL
或GREATER
,而不是 bool。不过没关系。正如 John 所说,当函数为空列表 well-defined 时,没有真正的理由使用模式
a :: b
。函数名称前缀
get
有点多余,因为所有(纯)函数的主要目的都是 something。您可以通过制作更高阶的变体来组合您的两个过滤函数:
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
似乎
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
尽管 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