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

[Twan van Laarhoven]

Bertram Felgenhauer wrote:
> finally, we could make it slightly more lazy, as follows:
> 
> (3)
>   subsequences :: [a] -> [[a]]
>   subsequences xs = [] : case xs of
>       []     -> []
>       (x:xs) -> tail (concatMap (\ys -> [ys, x:ys]) (subsequences xs))

You can get rid of the ugly call to 'tail':

     subsequences :: [a] -> [[a]]
     subsequences xs = [] : subsequences' xs
       where subsequences' []     = []
             subsequences' (x:xs) = [x] : concatMap (\ys -> [ys, x:ys])
                                                    (subsequences' xs)


> The only problem I see it that the output order is changed - does anybody
> feel that it is particularily important?

I don't think it matters much. This new version starts with things from 
the start of the list, as opposed to the end:

   subsequencesOld "abc" == ["","c","b","bc","a","ac","ab","abc"]
   subsequencesNew "abc" == ["","a","b","ab","c","ac","bc","abc"]

If anything, I think this makes more sense, especially since it works 
for infinite lists.

Twan