集合的应用实例（嵌套列表）

Question

我目前正在为我谨慎的数学做一个个人项目 class 并试图在 Haskell 中形式化集合论。我们 class 中定义的集合是特定宇宙元素的任意嵌套。我选择将其表示为事实上的标准嵌套列表：

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

作为一个懒惰的 Haskell 程序员，我想为所有标准类型class编写实例。

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

集合的应用实例（嵌套列表）

Applicative instance for sets (nested lists)

haskell

category-theory

applicative