集合ベース

http://www.kmonos.net/wlog/96.html#_1508090428への返答。

「集合」を明示的に値とするアプローチ [1] [2] だと、「同順の要素の並びはどちらでもいい」ソートアルゴリズムは、全ての可能なソート順の集合を返すことになると思います。

あくまでも仕様レベルの話をすると

「同順の要素の並びはどちらでもいい」ソートでは同順の要素に敢えて並びを与える必要はないと思います。むしろ「同順の要素の集合」を単位にソートする方が自然ではないでしょうか。下の表記はscheme風ですが、{}により集合を意図しています。

(sort-as-set '(A B D a C b c))
=> ({A a} {B b} {C c} {D});;「同順の要素の集合」の単位でソート
(unstable-sort '(A B D a C b c))
=> (A a B b C c D);;sort-as-setを平坦化

後半については「リストモナドは順序を備えている点が機能過剰であり、非決定性を閉じ込める先は集合モナドにするべきではないか？」というところです。

以下は独り言に近いけれど

「非決定性を導入した時点で既に従来の逐次処理との互換性がない。それなら並列前提の逐次処理にしてしまっても大差はないのではないか。集合ベース演算は並列性が極めて高く、メニーコアなら充分に速度を稼げる」という考え。