functional-programming - 扭曲的 SML 中的选择排序

Question

我开始对 sml 越来越熟悉，但是这个问题让我陷入了一个循环。我需要做的是在列表上执行选择排序，但扭曲的是所有偶数都需要进行奇数。

例如：

selSort[1, 6, 9, 3, 8, 4, 7, 2, 5, 3];
val it = [2, 4, 6, 8, 1, 3, 5, 7, 9] : int list

如果没有某种 for 循环或变量来帮助我，我无法解决这个问题。由于我是 sml 的新手，任何输入将不胜感激。谢谢！

Answer 1

函数式语言中的数据结构通常是不可变的；也就是说，它们一旦创建就无法修改。因此，您不能像在基于迭代数组的实现中那样执行就地交换。相反，您需要编写一个函数，它将您的原始列表作为参数，并返回它的独立副本以及您想要的更改。

例如，看一下内置函数rev。它返回您传递给它的任何列表的反转版本，但它不会（事实上，它不能）改变原始列表的结构。

在这种情况下，您可能需要一个函数min(xs)来查找 中的最小元素x，xs以及一个返回with removedremove(x,xs)副本的函数（我们称之为）。然后只需递归排序，并添加到结果中。xsxremainderremainderx

您可以通过定义自己的比较函数来强制执行这种不寻常的排序，而不是使用<to 比较元素，如果是偶数和奇数，则 where总是正确的。minlessThanlessThan(x,y)xy

fun lessThan(x,y) = (x mod 2 = 0 and y mod 2 = 1) or (x mod 2 = y mod 2 and x < y)

x < y现在只需将min(xs)函数中的任何实例替换为lessThan(x,y).

更好的是，编写一个selSort(list,comp)将比较函数comp作为参数的版本。然后你可以将它传递(op <)给执行标准排序，lessThan执行这种“扭曲排序”，甚至使用它对非整数列表进行排序（只要你给它一个具有相应类型的比较函数）。