適用於集合的實例（嵌套列表）

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