CODEWITHSUNDEEP
haskell
dopatraman
dopatraman

Reputation: 13908

All possible combinations of a list's elements

I need to get all possible combinations of a list's elements. I tried the solution here but it does not compile. Please help me figure this out:

subseq :: [a] -> [[a]]
subseq [] = []
subseq (x:xs) = map (x :) $ subseq xs

Basically this is a rewrite of the subsequences function in Data.List. I dont understand the version in the source though. My rationale behind the function above is this.

Apply the cons operator across all elements. This should produce a non deterministic result. However, the result I'm getting is an empty list. Please help.

Upvotes: 1

Views: 2191

Answers (2)

Redu
Redu

Reputation: 26161

You may also achieve this task with filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a] function which resides in Control.Monad. In this particular case our monad is list so we need a filtering function of type (a -> m Bool) which returns a list of boolean values. This could be \x -> [True, False] and the monad instance of list will apply them for each element of the provided list undeterministically and will result a list of lists.

Prelude> Control.Monad.filterM (\n -> [True, False]) [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

Upvotes: 0

mariosangiorgio
mariosangiorgio

Reputation: 5543

Let's start form the base case. The power set of the empty set is a set containing the empty set. So you need to replace subseq [] = [] with subseq [] = [[]]. Right now you're saying that the powers of an empty set is empty, which is not the case.

Your other case is missing something too. You need to change it to subseq (x:xs) = (subseq xs) ++ map (x :) (subseq xs). In plain english, this means that you take the subsets that don't contain the first item (subseq xs) and the subsets that contain it (map (x :) (subseq xs)).

If you omit the (subseq xs) part all you get is a list that contains only the original list because you only consider the sublist where you take every element.

Upvotes: 6

Related Questions