Data.List permutations

Slavomir Kaslev slavomir.kaslev at gmail.com
Wed Aug 5 09:04:56 EDT 2009


Thank you for the comprehensive reply Yitzchak.

On Wed, Aug 5, 2009 at 2:22 PM, Yitzchak Gale<gale at 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


More information about the Glasgow-haskell-users mailing list