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

[Bertram Felgenhauer]

David Benbennick wrote:
> Support, though I'd tweak the code in your patch a little:
> 
> subsequences            :: [a] -> [[a]]
> subsequences []         =  [[]]
> subsequences (x:xs)     =  let s = subsequences xs in s ++ map (x:) s

This will cause a space leak, as 's' will be kept around while its first
copy is consumed.

(1)
  subsequences (x:xs)     =  let s = subsequences xs
                             in  concatMap (\xs -> [xs, x:xs]) s

behaves better in that regard, but changes the order of the result lists.
This version can also be made to work for infinite lists with a small
modification,

(2)
  subsequences (x:xs)     =  let s = subsequences xs
                             in  [] : tail (concatMap (\ys -> [ys, x:ys]) s)

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))

I prever both (2) and (3) over (1) and the original, and I'm leaning
towards (3). (As an example where (3) is superior to (2), consider

  subsequences (1:2:undefined)  

(2) gives []:[1]:undefined, while (3) gives []:[1]:[2]:[1,2]:undefined)

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

Bertram