무료 모나드는 무엇입니까?

무료 모나드는 무엇입니까?

---

나는 용어를 본 적이 무료 모나드가 팝업 모든 현재 및 다음 몇 시간 동안, 그러나 모두는 / 사용 그들이 무엇인지에 대한 설명을 제공하지 않고 그것들을 논의 할 것으로 보인다. 무료 모나드는 무엇입니까? (저는 모나드와 하스켈 기본에 익숙하지만 범주 이론에 대한 지식은 매우 큽니다.)

---

Edward Kmett의 대답은 분명히 훌륭합니다. 그러나 약간 기술적 인 부분입니다. 여기 좀 더 접근하기 쉬운 설명이 있습니다.

무료 모나드는 펑터를 모나드로 바꾸는 일반적인 방법 일뿐입니다. 즉, 어떤 functor f Free f도 모나드입니다. 함수 쌍을 얻는 것을 제외하고는 매우 유용하지 않습니다.

liftFree :: Functor f => f a -> Free f a
foldFree :: Functor f => (f r -> r) -> Free f r -> r

이 중 첫 번째는 모나드에 "들어가"고 두 번째는 모나드에서 "나가"는 방법을 제공합니다.

보다 일반적으로, X가 여분의 물건 P를 가진 Y 인 경우, "자유로운 X"는 추가적인 것을 얻지 않고 Y에서 X로가는 방법입니다.

예 : monoid (X)는 기본적으로 추가 (생각을 생각할 수 있음) 및 일부 동일성 (0과 같은)이 있다고하는 추가 구조 (P)를 가진 집합 (Y)입니다.

그래서

class Monoid m where
   mempty  :: m
   mappend :: m -> m -> m

자, 우리 모두리스트를 알고 있습니다

data [a] = [] | a : [a]

음, 어떤 종류의 주어진 t우리가 알고 [t]모노 이드 인을

instance Monoid [t] where
  mempty   = []
  mappend = (++)

따라서 목록은 세트 (또는 하스켈 유형)에 대한 "자유 모노 이드"입니다.

무료 모나드는 같은 생각입니다. 우리는 functor를 가지고 모나드를 돌려줍니다. 실제로 모나드는 endofunctors 범주에서 monoid로 볼 수 있으므로 목록의 정의

data [a] = [] | a : [a]

무료 모나드의 정의와 매우 비슷합니다.

data Free f a = Pure a | Roll (f (Free f a))

그리고 Monad인스턴스에 유사성이 Monoid목록에 대한 인스턴스를

--it needs to be a functor
instance Functor f => Functor (Free f) where
  fmap f (Pure a) = Pure (f a)
  fmap f (Roll x) = Roll (fmap (fmap f) x)

--this is the same thing as (++) basically
concatFree :: Functor f => Free f (Free f a) -> Free f a
concatFree (Pure x) = x
concatFree (Roll y) = Roll (fmap concatFree y)

instance Functor f => Monad (Free f) where
  return = Pure -- just like []
  x >>= f = concatFree (fmap f x)  --this is the standard concatMap definition of bind

이제 두 가지 작업을 수행합니다

-- this is essentially the same as \x -> [x]
liftFree :: Functor f => f a -> Free f a
liftFree x = Roll (fmap Pure x)

-- this is essentially the same as folding a list
foldFree :: Functor f => (f r -> r) -> Free f r -> r
foldFree _ (Pure a) = a
foldFree f (Roll x) = f (fmap (foldFree f) x)

---

더 간단한 대답은 다음과 같습니다. Monad는 수도원 컨텍스트가 축소 될 때 "계산되는"것입니다 join :: m (m a) -> m a(호출을 >>=로 정의 할 수 있음 x >>= y = join (fmap y x)). 이것은 일련의 계산 체인을 통해 Monads가 컨텍스트를 전달하는 방법입니다. 시리즈의 각 지점에서 이전 호출의 컨텍스트가 다음 호출로 축소되기 때문입니다.

무료 모나드 모두 만족 모나드 법률은, 그러나 어떤 붕괴 (즉, 계산)을하지 않습니다. 단지 일련의 중첩 된 컨텍스트를 구축합니다. 이러한 자유 모나 딕 값을 생성하는 사용자는 이러한 중첩 된 컨텍스트로 무언가를 수행해야하므로 모나드 값이 생성 될 때까지 그러한 구성 의 의미 를 연기 할 수 있습니다.

---

무료 foo는 모든 'foo'법을 만족시키는 가장 간단한 것입니다. 다시 말해, 그것은 foo가되기 위해 필요한 법칙을 완벽하게 충족 시키며 추가적인 것은 아닙니다.

잊을 수없는 펑 터는 한 카테고리에서 다른 카테고리로 갈 때 구조의 일부를 "잊어 버린"사람입니다.

주어 펑 F : D -> C, 그리고 G : C -> D, 우리 말 F -| G, F수반 행렬을하기 위해 남아있는 G, 또는 G에서 오른쪽으로 수반 행렬이다 FFORALL A는, B는 때마다 : F a -> b에 동형 a -> G b화살표 적절한 범주 어디에서 왔는지.

공식적으로, 무료 functor는 잊혀진 functor에 인접 해 있습니다.

무료 모노 이드

더 간단한 예인 무료 모노 이드로 시작하겠습니다.

일부 이동 통신사 집합 T, 한 쌍의 요소를 함께 묶는 이진 함수 f :: T → T → T, 및 unit :: T연관 법칙 및 신원 법칙을 갖도록 정의 된 monoid를 사용하십시오 f(unit,x) = x = f(x,unit).

당신은 펑터를 할 수 있습니다 U(그들이지도 확인 화살표입니다, 모노 이드 homomorphisms 곳 monoids의 범주에서 unit로 unit다른 모노 이드에, 당신은 의미를 변경하지 않고 다른 모노 이드 매핑 이전 또는 이후에 구성 할 수 있음) 범주에 의 집합을 잊어 버린 unit캐리어 집합을 제공 하는 집합 (화살표는 단지 ​​기능 화살표)입니다 .

그런 다음 F집합 범주에서이 functor에 인접한 monoid 범주로 functor 를 정의 할 수 있습니다 . 이 functor는 집합 a을 monoid [a], where unit = []및로 매핑하는 functor입니다 mappend = (++).

pseudo-Haskell에서 지금까지의 예를 검토하십시오.

U : Mon → Set -- is our forgetful functor
U (a,mappend,mempty) = a

F : Set → Mon -- is our free functor
F a = ([a],(++),[])

그런 다음 F무료 로 표시 하려면 U잊어 버린 functor에 인접 해 있음을 보여 주어야합니다 . 즉, 위에서 언급했듯이

F a → b 동형이다 a → U b

이제 목표가 monoids F범주 Mon에 있다는 것을 기억하십시오 . 여기서 화살표는 monoid homomorphism입니다. 그래서 우리는 monoid homomorphism이 from [a] → b의 함수에 의해 정확하게 설명 될 수 있음 을 보여 주어야합니다 a → b.

하스켈에서 우리의 삶을 것을이의 측면 전화 Set(어, Hask그냥 우리는 척 것을 하스켈 유형의 범주가 설정이다) foldMap에서 전문, Data.Foldable목록에이 유형이를 Monoid m => (a → m) → [a] → m.

이것에 의해 부가적인 결과가 초래됩니다. 특히 잊어 버린 다음 무료로 구축 한 다음 다시 잊어 버린 경우 한 번 잊어 버린 것처럼 이것을 사용하여 모나드 조인을 구축 할 수 있습니다. UFUF~ U(FUF)~ 이후로 UF, 그리고 우리 는 우리의 부속물을 정의하는 동 형사상 [a]을 [a]통해 정체성 단일체 동 형사상을 전달할 수 있고,리스트 동 형사상 [a] → [a]이 유형의 함수 라는 것을 얻습니다. a -> [a]이것은 단지리스트를 반환합니다.

다음과 같은 용어로 목록을 설명하면이 모든 것을보다 직접 작성할 수 있습니다.

newtype List a = List (forall b. Monoid b => (a -> b) -> b)

무료 모나드

그렇다면 Free Monad 란 무엇입니까?

음, 우리는 이전과 똑같은 일을합니다. 화살표가 모나드 동질성 인 모나드 범주에서 화살표가 자연스런 변형 인 endofunctors 범주에 이르기까지 잊어 버린 functor U로 시작합니다. 그것에.

그렇다면, 이것은 일반적으로 사용되는 프리 모나드의 개념과 어떤 관련이 있습니까?

무언가가 자유 모나드라는 것을 아는 것은 Free f에서 모나드 동질 체를 얻는 Free f -> m것이에서 자연 변형 (functor homomorphism)을주는 것과 동일 하다는 것입니다 f -> m. 기억 F a -> b에 동형해야합니다 a -> U bF가 펑터를 U. U 여기에 매핑 된 모나드에 왼쪽 수반 행렬을 할 수 있도록.

F는 해커 지의 패키지에서 Free사용 하는 유형 과 최소한 동형 free입니다.

우리는 또한 자유 목록에 대한 위의 코드와 더 밀접하게 유사하게 구성 할 수 있습니다.

class Algebra f x where
  phi :: f x -> x

newtype Free f a = Free (forall x. Algebra f x => (a -> x) -> x)

코 프리 코 모나드

우리는 잊어 버린 functor가 존재한다고 가정하고 올바른 것을 보면서 비슷한 것을 만들 수 있습니다. cofree functor는 단순히 잊혀진 functor에 / right adjoint /이며, 대칭에 의해 cofree comonad라는 것을 아는 것은 comonad homomorphism을 얻는 w -> Cofree f것이에서 자연적으로 변형되는 것과 같은 것입니다 w -> f.

---

Free Monad (데이터 구조)는 List (데이터 구조)와 같은 Monad (클래스)에서 Monoid (클래스)까지입니다. 사소한 구현으로, 나중에 컨텐츠 결합 방법을 결정할 수 있습니다.

---

아마도 모나드가 무엇인지, 각 모나드는 fmap+ join+ return또는 bind+ 의 특정 (모나드 법 준수) 구현이 필요하다는 것을 알고있을 것입니다 return.

Functor (의 구현 fmap) 가 있다고 가정 하지만 나머지는 런타임에 선택한 값과 선택에 따라 달라집니다. 즉, Monad 속성을 사용할 수는 있지만 나중에 Monad 함수를 선택하려고합니다.

이것은 Free Monad (데이터 구조)를 사용하여 수행 할 수 있습니다.이 기능은 Functor (유형)를 감싼 join것보다 쌓아 놓는 방식으로 Functor (유형)를 포장합니다 .

실제 return와 join사용하려는 감소 기능에 매개 변수로 제공 할 수 있습니다 foldFree.

foldFree :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
foldFree return join :: Monad m => Free m a -> m a

유형을 설명하기 위해, 우리는 대체 할 수 Functor f와 Monad m와 b함께 (m a):

foldFree :: Monad m => (a -> (m a)) -> (m (m a) -> (m a)) -> Free m a -> (m a)

---

Haskell 프리 모나드는 functors의 목록입니다. 비교:

data List a   = Nil    | Cons  a (List a  )

data Free f r = Pure r | Free (f (Free f r))

Pure와 유사 Nil하고 Free유사합니다 Cons. 무료 모나드는 값 목록 대신 펑터 목록을 저장합니다. 기술적으로는 다른 데이터 유형을 사용하여 자유 모나드를 구현할 수 있지만 모든 구현은 위의 형식과 동형이어야합니다.

추상 구문 트리가 필요할 때마다 무료 모나드를 사용합니다. 자유 모나드의 기본 기능은 구문 트리의 각 단계 모양입니다.

누군가 이미 연결 한 내 게시물 은 무료 모나드를 사용하여 추상 구문 트리를 작성하는 방법에 대한 몇 가지 예를 제공합니다.

---

간단한 구체적인 예가 도움이 될 것이라고 생각합니다. 펑터가 있다고 가정 해 봅시다.

data F a = One a | Two a a | Two' a a | Three Int a a a

명백한 fmap. 그런 다음 Free F a잎 유형이 나무의 유형입니다 a누구의 노드와 태그와 One, Two, Two'과 Three. One-노드에는 하나의 하위가 있고 Two- Two'노드에는 두 개의 하위가 있고- Three노드에는 세 개의 하위 가 있으며 또한 태그가 있습니다 Int.

Free F모나드입니다. value가있는 잎 인 트리에 return매핑 x됩니다 x. t >>= f나뭇잎을보고 나무로 바꿉니다. 리프에 값이 y있으면 해당 리프를 트리로 바꿉니다 f y.

다이어그램은 이것을 더 명확하게하지만 쉽게 그릴 수있는 기능이 없습니다!

참고 URL : https://stackoverflow.com/questions/13352205/what-are-free-monads