選擇排序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執行這個「用扭曲排序」，甚至可以用它排序非整數列表（只要你給它一個相應類型的比較函數）。