Thank you for the comprehensive reply Yitzchak. On Wed, Aug 5, 2009 at 2:22 PM, Yitzchak Gale<[email protected]> wrote: > 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: > > http://hackage.haskell.org/package/combinat 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 _______________________________________________ Glasgow-haskell-users mailing list [email protected] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
