How do you 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?

---

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

---

Just another interesting solution:

filterM (const [True,False]) [1,2,3]

I read this as follows: Return the possible combinations of including or not including an element of the list. This explanation might not be using the correct terminology, but it's how I intuitively understand it. const evaluates to [True,False] for every element, so every element is included or not included in the result. Using filterM, the predicate here is in the list monad, so we get a list of the possible results.

---

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]

---

I really like the answer by @danlei for it's expressiveness (if you understand the non-determinism introduced by lists). But you don't need Monads for this. There is an applicative solution which also has that expressiveness while returning results in exactly the same order as the foldr based solution in the Data.List library.

subs [] = [[]]
subs (x:xs) = subs xs <**> [id, (x :)]

For me, once you understand how lists provide non-determinism (for which they much more powerful and useful than they are as a simple data structure), this is more immediately understandable than the foldr implementation.

It has two other interesting features compared to the library code:

1. It is simple to change it to replace : with any monoidal function (or to make it generic so that it can work with any monoid).
2. Also simple to change it to work with any foldable for which there is also a monoid instance (although any foldable has toList, so that's minor).

(Of course, the Data.List implementation, by using foldr, avoids external dependencies)

For example...

xorSubs [] = [0]
xorSubs (x:xs) = xorSubs xs <**> [id, xor x]

will efficiently calculate xor for all subsequences of a list. If a list contains multiple subsequences beginning with 1 : 2 (but only one instance of 1 and 2), xor 1 2 is calculated once and that value shared with all subsequences which contain 1 : 2. That is much more efficient than folding xor over each list in the output of subsequences.

Since 0 would be mempty for a monoid instance of xor, it shouldn't be hard to see how you could rewrite it as

msubs :: Monoid a => [a] -> [a]