セット（ネストされたリスト）の適用インスタンス

Question

私は現在、慎重な数学クラスのための個人的なプロジェクトに取り組んでおり、Haskellでセット理論を正式化しようとしています。私たちのクラスで定義されている集合は、特定の宇宙の要素の任意の入れ子です。私はすべての標準型クラス用のインスタンスを作成したい怠惰なHaskellのプログラマとして

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

：私はデファクトスタンダードネストされたリストとしてこれを表現することを選びました。

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) 

このインスタンスは、すべてのApplicativeの法律を満たす：

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