Аппликативный экземпляр для наборов (вложенные списки)

Question

В настоящее время я работаю над личным проектом для моего скромного класса математики и пытаюсь формализовать теорию множеств в Haskell. Набор, определенный в нашем классе, представляет собой произвольное вложение элементов конкретной вселенной. Я решил представить это в качестве стандартного вложенного списка де-факто:

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

Как ленивый программист Haskell я хочу написать примеры для всех стандартных классов типов.

Экземпляр Functor тривиальна:

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 и Traversable также относительно легко реализовать.

Не я застрял на Applicative. pure также проста:

instance Applicative Set where 
    pure x = Elem x Empty 

Однако я застрял на определении ap вложенных списков.

-- 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 ??? 

Для нормального, не вложен списка, аппликативный экземпляр принимает декартово произведение каждой функции с каждым элементом и применяет его:

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

Как-то вложенный список должен сохранить это базовая структура. Каков правильный экземпляр?

Answer 1

Ваш экземпляр почти правильно, только несколько больше предложений:

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) 

Этот экземпляр удовлетворяет все аппликативные законы:

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