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

[kahl at cas.mcmaster.ca]

Bertram Felgenhauer proposed the following version of subsequences:

 > 
 > (3)
 >   subsequences :: [a] -> [[a]]
 >   subsequences xs = [] : case xs of
 >       []     -> []
 >       (x:xs) -> tail (concatMap (\ys -> [ys, x:ys]) (subsequences xs))

I think that lazyness is attractive, and sequence of results is
unimportant, so agree with his choice of (3).

I see additional improvements in saving the tail:


subsequences, nonEmptySubsequences :: [a] -> [[a]]
subsequences xs = [] : nonEmptySubsequences xs

nonEmptySubsequences [] = []
nonEmptySubsequences (x:xs) = [x] :
    -- concatMap (\ ys -> [ys, x:ys]) (nonEmptySubsequences xs)
    foldr f [] (nonEmptySubsequences xs)
  where f ys r = ys : (x : ys) : r


Testing this with:


main = do
  a : _ <- getArgs
  putStrLn $ show $ sum $ map sum $ subsequences [1 .. read a]

and ghc-6.8.2 -O produces the following user times
(minimum out of five runs) for argument 24 for the two variants:

foldr      6.796s
concatMap  8.044s

So eliminating (++) clearly pays off, too.



Wolfram