자유 그룹 모나

Question

카테고리 이론에서 monad은 두 개의 adjoint 펑터의 구성입니다. 예를 들어 Maybe 모나드는 잊혀진 펑터로 구성된 무료 첨자 세트 펑터입니다. 마찬가지로, List 모나드는 잊혀진 functor로 구성된 무료 monoid functor입니다.

모노 노이드는 가장 간단한 대수 구조 중 하나입니다. 그래서 프로그래밍이 더 복잡한 것들로부터 이익을 얻을 수 있는지 궁금합니다. 나는 표준 하스켈 패키지에서 무료로 그룹 모나드를 찾지 못했습니다, 그래서 나는

data FreeGroup a = Nil | PosCons a (FreeGroup a) | NegCons a (FreeGroup a) 

== 운영자

가 NegCons x (PosCons x y) == y하도록 정의 여기를 정의 할 수 있습니다. 따라서 length :: FreeGroup a -> Int에서 각 PosCons은 +1로 계산되고 각 숫자는 NegCons -1입니다 (이는 각 PosCons에서 +1 값을 갖는 Int의 유일한 그룹 모프입니다).

목록 (무료 monoids)에서와 같이 concat은 곱셈이며 map은 재미있는 함수입니다. 따라서 FreeGroup의 모나드 인스턴스는 List의 모나드 인스턴스와 정확히 같습니다.

무료 그룹 모나드는 프로그래밍 용도로 사용됩니까? 또한 종종 모나드를 컨텍스트에서 값으로 해석하는 경우가 있습니다. List의 경우 컨텍스트는 선택 또는 불확실성입니다. 자유 집단 모나드에 대한 그러한 해석이 있습니까?

무료 링 및 벡터 공간은 언제나 무료입니다.

foldS :: S s => (a -> s) -> FS a -> s 

그것은 자유 물체상의 S -morphism에 기초 a에 함수 리프트 : 모두 대수적 구조 S 들어

는 categorical free functor FS :: Set -> S 존재 하스켈 폴드 호출 기능의 존재를 의미 FS a. 보통 foldr 함수는 foldMonoid (하스켈에서 foldMap이라고 불리는 이유는 무엇인가)의 특수화이며, monoid는 곱셈과 같은 조합으로 구성된 함수 집합 b -> b입니다. 완성도를 위해서

, 여기 FreeGroup의 모나드 인스턴스 : "자유 그룹 모나드가 어떤 프로그래밍 사용이 있습니까"

mult :: FreeGroup a -> FreeGroup a -> FreeGroup a 
mult Nil x = x 
mult x Nil = x 
mult (PosCons x y) z = PosCons x (mult y z) 
mult (NegCons x y) z = NegCons x (mult y z) 

inverse :: FreeGroup a -> FreeGroup a 
inverse Nil = Nil 
inverse (PosCons x y) = mult (inverse y) (NegCons x Nil) 
inverse (NegCons x y) = mult (inverse y) (PosCons x Nil) 

groupConcat :: FreeGroup (FreeGroup a) -> FreeGroup a 
groupConcat Nil = Nil 
groupConcat (PosCons x l) = mult x (groupConcat l) 
groupConcat (NegCons x l) = mult (inverse x) (groupConcat l) 

instance Functor FreeGroup where 
    fmap f Nil = Nil 
    fmap f (PosCons x y) = PosCons (f x) (fmap f y) 
    fmap f (NegCons x y) = NegCons (f x) (fmap f y) 

instance Applicative FreeGroup where 
    pure x = PosCons x Nil 
    fs <*> xs = do { f <- fs; x <- xs; return $ f x; } 

instance Monad FreeGroup where 
    l >>= f = groupConcat $ fmap f l 

Answer 1

지난 4 개월 동안 답변이 없기 때문에 대답은 '아니오, 실제로는 아닙니다'라고 가정합니다. 그러나 그것은 흥미로운 질문입니다. 그리고 그것은 기본적인 수학 개념에 기초를두고 있기 때문에 그것이 나에게 (또한) 있어야한다고 생각합니다.

우선 나는 우리의 무료 그룹이 단지를

type FreeGroupT a = [Either a a] 

fgTofgT :: FreeGroup a -> FreeGroupT a 
fgTofgT Nil = [] 
fgTofgT (a :+: as) = Right a : fgToList as 
fgTofgT (a :-: as) = Left a : fgToList as 

fgTTofg :: FreeGroupT a -> FreeGroup a 
fgTTofg [] = Nil 
fgTTofg (Right a : as) = a :+: fgTTofg as 
fgTTofg (Left a : as) = a :-: fgTTofg as 

--using (:-:) instead of NegCons 
--and (:+:) instead of PosCons 

우리가 확인하기 때문에이 멋진 정의는 것을 제안 무료 그룹 기능도 그냥 간단하게 하나의 AA의 목록과 함께 구현 될 수 있습니다 약간의 여분의 구조를 가진 모노로이드. 자유 그룹은 다른 펑터가있는 무료 모노 노드의 구성 일뿐입니다 (이름은 무엇입니까? b bifunctor가 아닌 Functor F a = L a | R a). 또한 자유 그룹 모나드 인스턴스가 자유 모노 노드의 모나드 인스턴스와 일치하는지 확인합니다.즉, 자유 그룹의 모나드는 모두 양수가되는 용어로 작동해야하며, 자유 모노 노드보다 모나드처럼 행동해야합니다. 맞습니까?

그러나 역수를 줄이려면 Eq a 인스턴스가 필요합니다. 우리는 학기 수준에서 일해야하며, 순수한 유형 수준의 정보로는 충분하지 않습니다. 이것은 자유 수준의 monoid와 자유 그룹 사이의 타입 레벨 차이를 도움이되지 않게합니다 - 제가 볼 수있는 한. 적어도 의존성 타이핑은하지 않아도됩니다.

실제 프로그래밍 사용에 대한 설명을 위해 필자는 그럴듯한 사용 사례를 제공하려고 시도하지만 실패합니다.

"Ctrl"키를 사용하여 명령 시퀀스를 알리는 텍스트 편집기를 상상해보십시오. "Ctrl"을 누른 상태에서 누른 키 시퀀스는 FreeGroup에서 음수 (negative cons (: - :))로 모델링됩니다. 따라서 자유 그룹이라는 용어 인 'a':+:'b':+:'b':-:'a':-:[]은 "ab"라고 쓰는 emacs 동작을 모델링하는 데 사용할 수 있습니다. 커서를 문자로 이동 한 다음 줄의 처음으로 이동합니다. 그런 디자인이 좋다. 특수 예약 이스케이프 문자없이 스트림에 명령과 매크로를 쉽게 포함시킬 수 있습니다.

그러나이 예제는 'a':+:'b':+:'b':-:'a':-:[]이 []과 동일한 프로그램이 될 것으로 예상하므로 적절한 사용 사례로 실패합니다. 게다가, 위의 논의 에서처럼 각각의 목록 용어를 단순히 래핑하는 것만으로도 충분합니다.