Блог

В настоящее время я работаю над личным проектом для своего класса по математике и пытаюсь формализовать теорию множеств в 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]
  

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

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

 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