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? Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe