Haskell – How to find all of the subsequences of a list


I'm trying to learn how to list comprehension and I'm trying to figure out a way to find all the subsequences of a list but i'm not quite sure how one would go about that. Could anyone help me?

Best Solution

If you want access to this functionality, you can use the subsequences function that is in Data.List.

subsequences [1,2,3]
>>> [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

If you want to know how it's implemented, you can check the function's source code, which is available on Hackage.

In this case, it's:

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

nonEmptySubsequences         :: [a] -> [[a]]
nonEmptySubsequences []      =  []
nonEmptySubsequences (x:xs)  =  [x] : foldr f [] (nonEmptySubsequences xs)
  where f ys r = ys : (x : ys) : r
Related Question