Applicative instance for sets (nested lists)

Question

I am currently working on a personal project for my discreet maths class and am trying to formalize set theory in Haskell. A set as defined in our class is an arbitrary nesting of elements of a particular universe. I chose to represent this as the de facto standard nested list:

data Set a where
  Empty :: Set a
  Elem  ::   a   -> Set a -> Set a
  Set   :: Set a -> Set a -> Set a

As a lazy Haskell programmer I want to write instances for all the standard typeclasses.

The Functor instance is trivial:

instance Functor Set where
  fmap _ Empty        = Empty
  fmap f (Elem x set) = Elem (f x) set
  fmap f (Set s set)  = Set (fmap f s) $ fmap f set

Foldable and Traversable are also relatively easy to implement.

Not I'm stuck on Applicative. pure is also straightforward:

instance Applicative Set where
  pure x = Elem x Empty

However, I'm stuck on defining ap for nested lists.

-- set has a monoid instance
(<*>) :: Set (a -> b) -> Set a -> Set b
Elem fx  fxs  <*> x = fmap fx x `mappend` (fxs <*> x)
Set  fxs fxss <*> x = Set ???

For a normal, not nested list, the applicative instance takes the cartesian product of every function with every element and applies it:

fx <*> xs = [f x | f <- fx, x <- xs]

Somehow the nested list must preserve it's underlying structure. What is the correct instance?

Answer 1

Your instance is almost correct, just a few more suggestions:

instance Applicative Set where
  pure x = Elem x Empty
  -- the cartesian product of the empty set and x is empty
  Empty         <*> x = Empty
  -- the cartesian product of x and the empty set is empty
  x             <*> Empty = Empty
  -- if you encounter a function, apply it to the entire list
  -- and append the result of the recursive call to the rest.
  Elem fx  fxs  <*> x = fmap fx x `mappend` (fxs <*> x)
  -- If you reach a level of nesting, go into the nested list
  -- and prepend that to the rest.
  Set  fxs fxss <*> x = Set (fxs <*> x) (fxss <*> x)

This instance satisfies all the applicative laws:

pure id  <*> x      = x
pure f   <*> pure x = pure $ f x
pure (.) <*> pure u <*> pure v <*> pure w = u <*> (v <*> w)
u        <*> pure y = pure ($ y) <*> u