私は現在、慎重な数学クラスのための個人的なプロジェクトに取り組んでおり、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]
どういうわけか、ネストされたリストが、それは根本的な構造だ保持する必要があります。 正しいインスタンスは何ですか?