On Jul 28, 2009, at 10:04 AM, Jan Christiansen wrote:
> I especially like the implementation of perms by means of sortBy.
Very nice indeed!
I wonder with which implementations of sort this works. Sorting
usually requires that the given predicate is an ordering relation and
specific efficient sorting functions may be only justified if it is.
QuickSort relies on transitivity, I feel that this may lead to only a
subset of permutations being generated by |quickSortBy (\_ -> True ?
False)|. And what about mergeSort? The final merge step may allow to
generate all permutations (?)
So here are interesting questions: what property must a sorting
function satisfy such that |sortBy (\_ -> True ? False) yields all
permutations? Or does it work for any sorting function? Why?
Cheers,
Sebastian
--
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Di Jul 28 2009 - 11:02:15 CEST