Thank you for the comprehensive reply Yitzchak.
On Wed, Aug 5, 2009 at 2:22 PM, Yitzchak Galeg...@sefer.org 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
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
