On 15/09/2015, at 6:57 am, JORGE MALDONADO
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?