Data.List permutations

[Slavomir Kaslev]

On Tue, Aug 4, 2009 at 8:42 PM, Slavomir
Kaslev<slavomir.kaslev at gmail.com> wrote:
> A friend mine, new to functional programming, was entertaining himself by
> writing different combinatorial algorithms in Haskell. He asked me for some
> help so I sent him my quick and dirty solutions for generating variations and
> permutations:
>
>> inter x [] = [[x]]
>> inter x yys@(y:ys) = [x:yys] ++ map (y:) (inter x ys)
>
>> perm [] = [[]]
>> perm (x:xs) = concatMap (inter x) (perm xs)
>
>> vari 0 _ = [[]]
>> vari _ [] = []
>> vari k (x:xs) = concatMap (inter x) (vari (k-1) xs) ++ vari k xs
>
> After that I found out that nowadays there is a permutation function in the
> Data.List module:
>
>> permutations            :: [a] -> [[a]]
>> permutations xs0        =  xs0 : perms xs0 []
>>   where
>>     perms []     _  = []
>>     perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
>>       where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
>>             interleave' _ []     r = (ts, r)
>>             interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
>>                                      in  (y:us, f (t:y:us) : zs)
>
> I was surprised to find that not only my version is much simpler from the one
> in Data.List but it also performs better. Here are some numbers from my rather
> old ghc 6.8.1 running ubuntu on my box:
>
> *Main> length $ permutations [1..10]
> 3628800
> (10.80 secs, 2391647384 bytes)
> *Main> length $ perm [1..10]
> 3628800
> (8.58 secs, 3156902672 bytes)
>
> I would like to suggest to change the current implementation in Data.List with
> the simpler one. Also, it would be nice to add variations and combinations in
> the Data.List module.
>
> Cheers.
>
> --
> Slavomir Kaslev
>

Oops. It seems I should have used the glasgow-haskell-users mailing list.
FIXED

-- 
Slavomir Kaslev