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