[Haskell-cafe] powerSet = filterM (const [True,
False]) ... is this obfuscated haskell?
Sebastian Fischer
sebf at informatik.uni-kiel.de
Tue Jul 28 09:47:53 EDT 2009
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.)
More information about the Haskell-Cafe
mailing list