選択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 

私は、私を支援するために、ループや変数のいくつかの並べ替えをせずにこれをやって周りに私の頭を取得することはできません。私がsmlに慣れているので、どんなインプットも高く評価されます。ありがとう！

Answer 1

機能的な言語のデータ構造は、一般に不変です。つまり、一度作成されると変更することはできません。したがって、反復配列ベースの実装のように、インプレーススワップを実行することはできません。代わりに、元のリストを引数として取る関数を記述し、それを独立したコピーで返します。

たとえば、組み込み関数revを見てください。それはあなたがそれを渡すリストの逆のバージョンを返しますが、元のリストの構造を変更しません（実際にははではありません）。この場合

、あなたはおそらくxsで最小の要素xを見つけるために、機能min(xs)をしたい、と削除xでxsのコピーを返す関数remove(x,xs)（のはremainderそれを呼びましょう）。次に、再帰的にremainderを並べ替え、その結果の前にxを追加します。

代わりminに要素を比較する<を使用するのでは、あなたがxが偶数で、yが奇数の場合lessThan(x,y)は常に真である、独自の比較関数lessThanを定義することによって、この異常な順序付けを実施することができます。

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のすべてのインスタンスを置き換えます。

さらに、比較機能compを引数として使用するバージョンselSort(list,comp)を作成してください。次に、(op <)を渡して、標準ソートlessThanを実行してこの「並べ替えで並べ替える」、または非整数リストをソートすることもできます（対応するタイプの比較関数を与えている限り）。