[Haskell-cafe] Powerset of a set

[Richard A. O'Keefe]

On 15/09/2015, at 6:57 am, JORGE MALDONADO <jorgemal1960 at gmail.com> wrote:

> The powerset of set s is a set containing all subsets of s.
> I need a clue on how to write Haskell code to get the superset of a set using direct recursion and list comprehension.


Here is a clue.
>> The question is not well posed.

What is the representation of sets going into your function?
What is the representation of sets coming out of your function?

You could, for example, perform the operation in constant time
by playing games with representations: given a representation of
a set, return a wrapper containing that represent

   typeclass Eq t => Set t
      where is_element :: t -> Set t -> Bool

   instance Eq t => Set [t]
      where is_element = elem

   newtype Power t = Power t

   instance Set t => Set (Power t)
      where is_element x (Power s) = is_subset x s

(Very rough sketch done in haste.)  We can throw in a direct
recursion (in the definition of is_subset, perhaps) and a list
comprehension if you like.

I am not suggesting that you *should* do this, but that your
problem as stated *does not rule this out* as (the beginnings of)
an answer.

So start by spelling out what you are going to use to represent
a set and *how* one of those represents the set it does.  Then
think about the calculation you want to do *in terms of sets*,
not your representation.

 P {} = {{}}
 P ({x} U s) = something involving x, s, and P s.

You also need to be clear about what it is that you are doing.
Are you building some code that you expect to use in a real
program?  In that case, what is this going to cost you?  (Hint:
if |s| = n, what is |P s|?)  If you are doing homework, what is
going to get you marks?  Surely, it is demonstrating understanding.
In this case, yo seem to be asked to show that you understand
recursion, and list comprehensions.

The (incomplete) definition of the power set of a finite set
given above (P) is naturally recursive.  What makes it a good
recursion is that the cases are clearly distinct and the
recursive call (P s) has an argument that is strictly smaller
than what you started with ({x} U s) provided of course that
x is not an element of s.  What makes it a questionable definition
is that it seems to depend on which x we pick.  But does it?
You need to *argue* that

   P({}) = {{}}
   P({x} U s) = something involving x, s, and P(s)
      for *any* partition of a non-empty set n into {x} and s = n\{x}.

Then your code can pick whatever x is easiest to find in the
data structure you're using to represent a set.

Final thought.
If  p1 [1,2] = [[],[1],[2],[1,2]]
and p2 [1,2] = [[2,1],[2],[1],[]]
are they *both* good answers, or neither, or just one?