Haskell Power Set Function

Question

I get an error:

working.hs:186:25: error:
* Couldn't match expected type: Set (Set a)
              with actual type: [[a]]
* In the expression:
    union (map (insert x) (powerSet s)) (powerSet s)
  In an equation for `powerSet':
      powerSet (Node x s)
        = union (map (insert x) (powerSet s)) (powerSet s)
* Relevant bindings include
    s :: Set a (bound at working.hs:186:20)
    x :: a (bound at working.hs:186:18)

working.hs:186:48: error:
* Couldn't match expected type: [[a]]
              with actual type: Set (Set a)
* In the second argument of `map', namely `(powerSet s)'
  In the first argument of `union', namely
    `(map (insert x) (powerSet s))'
  In the expression: union (map (insert x) (powerSet s)) (powerSet s)
* Relevant bindings include
    s :: Set a (bound at working.hs:186:20)
    x :: a (bound at working.hs:186:18)

working.hs:186:62: error:
* Couldn't match expected type: [[a]]
              with actual type: Set (Set a)
* In the second argument of `union', namely `(powerSet s)'
  In the expression: union (map (insert x) (powerSet s)) (powerSet s)
  In an equation for `powerSet':
      powerSet (Node x s)
        = union (map (insert x) (powerSet s)) (powerSet s)
* Relevant bindings include
    s :: Set a (bound at working.hs:186:20)
    x :: a (bound at working.hs:186:18)

Failed, no modules loaded.

My function is:

powerSet :: Set a -> Set (Set a)
powerSet EmptyS = singleton EmptyS
powerSet (Node x s) = union (map (insert x) (powerSet s)) (powerSet s)

Why do I get the error?

Answer 1

As other contributors have mentioned in the comments to the question, map only works on lists. To "map" insert x over powerSet s, you would have to create a functor instance for the Set type, then use fmap instead.

instance Functor Set where
    fmap f EmptyS      = EmptyS
    fmap f (Node x s') = Node (f x) (fmap f s')

Then you would have:

powerSet :: Ord a => Set a -> Set (Set a)
powerSet EmptyS = singleton EmptyS
powerSet (Node x s') = union (fmap (insert x) (powerSet s')) (powerSet s')

I did not see your code for singleton, so I will include mine for completeness.

singleton :: Ord a => a -> Set a
singleton x = Node x EmptyS

I notice your type signature for powerSet does not include the Ord a constraint. You will need this since insert requires Ord a. Then in order to use it on sets themselves you will also have to define instances of Ord and Eq for Set a. This is fairly straightforward:

instance (Ord a) => Eq (Set a) where
  (==) EmptyS EmptyS = True
  (==) EmptyS _      = False
  (==) _ EmptyS      = False
  (==) s0 s1         = (toList s0) == (toList s1)

instance (Ord a) => Ord (Set a) where
  compare s0 s1 = compare (toList s0) (toList s1)