On Jul 28, 2009, at 11:06 AM, Sittampalam, Ganesh wrote:

perms = sortByM (const [True,False])

This doesn't seem right, since the comparison function is inconsistent

I was also wary about this point, e.g. QuickSort depends on transitivity.

and moreover the results will depend on the sorting algorithm chosen.

Is it only that different sorting algorithms enumerate all permutations in different orders or is there a sorting algorithm, such that the above definition does not enumerate all permutations?

Here is some shirt-sleeved reasoning:

Every sorting algorithm :: [Int] -> [Int] that actually sorts can describe every possible permutation (if there is a permutation that cannot be realised by the sorting algorithm then there is an input list that cannot be sorted). Hence, if this sorting algorithm is `sortBy p` for some predicate p then there are possible decisions of p to produce every possible permutation. If p makes *every* decision non- deterministically then certainly the specific decisions necessary for any specific permutation are also made.

Hence, perm as defined above can yield a list that contains all permutations of the input (at least once) regardless of the sorting algorithm.

Where is the hitch?


Underestimating the novelty of the future is a time-honored tradition.

Haskell-Cafe mailing list

Reply via email to