选择排序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和功能remove(x,xs)返回的xs一个副本x删除（姑且称之为remainder）。然后只是递归地对remainder进行排序，并在结果前面加上x。

而不是使用<在min比较的元素，你可以定义自己的比较函数lessThan，其中lessThan(x,y)始终是真，如果x是偶数和y是奇数强制执行此排序不正常。

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

现在只是lessThan(x,y)替换您min(xs)功能x < y任何实例。

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