Thank you for the comprehensive reply Yitzchak.
On Wed, Aug 5, 2009 at 2:22 PM, Yitzchak Gale
Hi Slavomir,
Slavomir Kaslev wrote:
inter x [] = [[x]] inter x yys@(y:ys) = [x:yys] ++ map (y:) (inter x ys)
perm [] = [[]] perm (x:xs) = concatMap (inter x) (perm xs)
I was surprised to find that not only my version is much simpler from the one in Data.List but it also performs better. I would like to suggest to change the current implementation in Data.List with the simpler one.
Thanks for looking into this.
A lot of work went into the permutations function in Data.List, most of it by Twan van Laarhoven, including studying the order in which the permutations are returned, laziness, and extensive performance testing. The result was compared against Knuth's algorithmic work on this topic.
Your algorithm is indeed similar to one that was considered during that development process.
See the following thread for the details:
http://www.haskell.org/pipermail/libraries/2007-December/008788.html
and continued in:
http://www.haskell.org/pipermail/libraries/2008-January/008859.html
Thanks for the links. I didn't realize how much effort and considerations have gone in the development of permutations. I should have guessed better. One can never determine the effort that certain code needed to be developed from the code itself.
Things do change with time, so it's always worthwhile to revisit these things and not take them for granted. If you can improve on this work, please let us know on the libraries mailing list.
I should have sent the message to the libraries mailing list in the first place. But I was under the (outdated) impression that Data.List is ghc specific library. For a possible improvement, I guess I have to work harder to outdo the work that went into permutations. While this is a noble goal, it wasn't my initial intention. I was just helping a friend. Although, I may get onto it when I have enough spare time (I am preparing for my graduation exam in the moment).
Also, it would be nice to add variations and combinations in the Data.List module.
Personally, I disagree. I think those should go in a separate combinatorics library, not Data.List. As an example, take a look at the combinat package on Hackage:
You are right. There's no reason to bloat Data.List with such functions, when a different module will do. Thanks for the link. Cheers. -- Slavomir Kaslev