haskell - 集合的应用实例(嵌套列表)

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

对于一个普通的、非嵌套的列表，applicative 实例采用每个函数与每个元素的笛卡尔积并应用它:

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