집합 (중첩 목록)에 대한 적용 인스턴스

Question

현재 신중한 수학 수업을위한 개인 프로젝트를 진행 중이고 하스켈에서 집합 이론을 형식화하려고합니다. 이 클래스에서 정의 된 집합은 특정 유니버스의 임의의 요소 중첩입니다. 나는 사실상의 표준 중첩 된 목록으로이를 표현하기 위해 선택 :

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

을 내가 모든 표준 typeclasses에 대한 인스턴스를 작성하려는 게으른 하스켈 프로그래머.

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