Add 'subsequences' and 'permutations' to Data.List (ticket #1990)

Twan van Laarhoven twanvl at
Wed Dec 19 19:57:07 EST 2007

David Benbennick wrote:
> Actually, I would like permutations to satisfy:
>   map (take n) (take (factorial n) $ permutations [1..]) == permutations [1..n]
> Not only is that a neat property, but it forces maximal laziness.

That would indeed be nice. After a lot of work I have come up with a 
function that does this:

   permutations4 xs = perms xs [[]] []
     perms xxs ps qs = map (++xxs) ps
                    ++ case xxs of
                          []     -> []
                          (x:xs) -> perms xs
                                    (concatMap (interleave x) (ps ++ qs))
                                    (map (++[x]) (ps ++ qs))
     interleave x []      =  []
     interleave x (y:ys)  =  (x:y:ys) : map (y:) (interleave x ys)

Unfortunatly this function is really slow, 10.734375 sec, compared to 
3.875000 sec for the initial version (see previous message for details 
of testing). This is of course the result of way too many (++) calls.


More information about the Libraries mailing list