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

[Twan van Laarhoven]

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 [[]] []
    where
     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.

Twan