[Haskell-cafe] powerSet = filterM (const [True, False]) ... is this obfuscated haskell?

[Sebastian Fischer]

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.)