Data.List permutations

[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

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.

> 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

But you don't have to agree with me. If you think that they
should go into Data.List, propose it using the following procedure:

http://www.haskell.org/haskellwiki/Library_submissions

Regards,
Yitz