How do you find all of the subsequences of a list?

Question

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?

Answer 1

Ezra's answer covers all subsequences, but if you just want the continuous sub-sequences, you can use:

import Data.List
continuousSubSeqs = filter (not . null) . concatMap inits . tails

I.e you get

Prelude Data.List> continuousSubSeqs "asdf"
["a","as","asd","asdf","s","sd","sdf","d","df","f"]

The above can be written as a list comprehension as well:

import Data.List
continuousSubSeqs ls = [t | i <- inits ls, t <- tails i, not $ null t]

Answer 2

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