Powerset of a set with list comprehension in Haskell

Question

I am a complete beginner in Haskell and I have 11 exercises for homework, 10 of which I have already solved. I have found several solutions to get the powerset of a set, but none of them includes list comprehension. I know I should not ask for a complete answer in this case (because it is homework) but I would very much appreciate any feedback/clue.

The powerset of set S is a set containing all subsets of S. Write a recursive function powerset that returns a set containing all subsets of a given set. Use direct recursion and list comprehension.

Pickaxe

It's fine not to get all of the homework problems. 10 out of 11 is great work by any measure! You'll learn the best by giving it your best shot yourself and then seeing what the answer is which I'm sure they will go over in class. – Hyperbaric

Have you tried looking at one of the solutions that doesn't use list comprehension and converting it to do so? You will probably learn a lot even if you don't implement the power-set algorithm totally on your own. – Mogerly

Answer 1

Using direct recursion and list comprehension:

type Set a = [a]

powerset :: Set a -> Set (Set a)
powerset [] = [[]]
powerset (x:xs) = [x:ps | ps <- powerset xs] ++ powerset xs

Cletuscleve

@WillNess I got it working by doing this, but if your suggestion can make it less redundant, feel free to edit it. – Cletuscleve

are you sure it's working? it doesn't for me: lpaste.net/199034 . And what is Set? – Ballista

Try the updated solution @WillNess Also: type Set a = [a] – Cletuscleve

now it's OK. -- it's also [r | ps<-powerset xs, r<-[(x:ps),ps]], for your amusement; but your version might be less memory hungry. – Ballista

Answer 2

Ok here is my go at a hint:

If you look at something like (x:xs) you now have a choice to either include x in your subset or not.

Somehow have to use both choices (probably with (++) ;)) ...

Now remember the other hints (recursion ... xs ....) and maybe you get an idea if you think about [x:ys | ys <- ...]

---

BTW: it's almost cheating but if you found a solution using do notation: this is really easy to translate into list comprehensions ;) - maybe you can post your progress a bit?

Jerriejerrilee

Actually I am analizing the following solution I got from our class forum but I do not know what f = (:) x means, can you please explain? I perfectly understand the rest of the code: powerSet (x:xs) = map f p ++ p where p = powerSet xs f = (:) x powerSet [] = [[]] – Pickaxe

@Pickaxe yes I can: (:) x = \ys -> [ x:y | y <- ys] - see (:) is the cons operator you already know from lists: (:) x xs = x:xs and there is even a syntax that is easier to crasp (called a section): (:) x = (x:) – Jerriejerrilee

Answer 3

The text says "use direct recursion". So, when you need to compute subsets (x:xs) you can start with considering subsets xs as a recursive call. Is there any way to turn the subsets of xs into those of x:xs, perhaps using list comprehensions?

Cardoon