모나드는 endofunctor 범주의 모노 이드 일뿐입니다. 무엇이 문제입니까?

모나드는 endofunctor 범주의 모노 이드 일뿐입니다. 무엇이 문제입니까?

---

누가 먼저 다음과 같이 말했습니까?

모나드는 endofunctor 범주의 모노 이드 일뿐입니다. 무엇이 문제입니까?

그리고 덜 중요한 점에서, 이것이 사실입니까? 그렇다면 설명을 해주실 수 있습니까 (하스켈 경험이 많지 않은 사람이 이해할 수 있기를 바랍니다)?

---

그 특별한 표현은 James Iry의 매우 재미있는 Brief, Incomplete 및 Mostly Wrong History of Programming Languages 에서 Philip Wadler에게 허구로 언급 한 것입니다.

원본 인용문은 범주 이론의 기본 텍스트 중 하나 인 일하는 수학자를위한 범주의 손더스 맥 레인에서 발췌 한 것입니다. 이것이 의미하는 바를 정확히 배울 수있는 가장 좋은 장소 인 문맥 에 있습니다.

하지만 찌르겠습니다. 원래 문장은 다음과 같습니다.

모두 말하면, X의 모나드는 X의 엔도 펑터 범주의 모노 이드 일 뿐이며, 제품 ×는 엔도 펑터의 구성과 정체성 엔도 펑터에 의해 설정된 단위로 대체됩니다.

X 는 카테고리입니다. Endofunctor는 카테고리에서 그 자체로의 펑터입니다 ( 함수 프로그래머가 관심을 갖는 한 일반적으로 모두 Functor 하나의 카테고리, 유형의 카테고리 만 다루기 때문에 모든 것입니다. 그러나 당신은 " X의 엔도 펑터"의 범주 인 다른 범주를 상상할 수 있습니다. 이것은 객체가 endofunctor이고 형태가 자연스러운 변형 인 범주입니다.

그리고 그 endofunctor 중 일부는 모나드 일 수 있습니다. 어떤 것이 모나드입니까? 특정 의미에서 정확히 단일형 인 것입니다 . 모나드에서 모노 이드로의 정확한 매핑을 철자하는 대신 (Mac Lane이 내가 바라는 것보다 훨씬 낫기 때문에) 각각의 정의를 나란히 놓고 비교할 수 있습니다.

모노 이드는 ...

• A 세트, S
• 작업, • : S × S → S
• S , e : 1 → S 의 요소

... 다음 법률을 충족 :

• (a • b) • c = a • (b • c) , S의 모든 a , b 및 c 에 대해
• e • a = a • e = a , S의 모든 a 에 대해

모나드는 ...

• endofunctor, T : X → X (하스켈에서 인스턴스 * -> *가있는 종류의 생성자 Functor)
• 자연스러운 변환, μ : T × T → T , 여기서 × 는 펑터 구성을 의미합니다 ( μ 는 joinHaskell에서 알려짐 )
• 자연스러운 변환, η : I → T , 여기서 I 는 X 의 정체성 엔도 펑터입니다 ( η 는 returnHaskell에서 로 알려져 있습니다 )

... 다음 법률을 충족 :

• μ ∘ Tμ = μ ∘ μT
• μ ∘ Tη = μ ∘ ηT = 1 (정체 자연 변환)

약간의 곁눈질로이 두 정의가 모두 동일한 추상 개념의 인스턴스임을 알 수 있습니다 .

---

직관적으로, 멋진 수학 어휘가 말하는 것은 다음과 같습니다.

모노 이드

모노 이드는 객체의 세트, 및 이들을 조합 한 방법이다. 잘 알려진 모노 이드는 다음과 같습니다.

• 추가 할 수있는 번호
• 연결할 수있는 목록
• 조합 할 수있는 세트

더 복잡한 예도 있습니다.

또한 모든 모노 이드에는 정체성 이 있습니다. 즉, 다른 것과 결합 할 때 효과가없는 "no-op"요소입니다.

• 0 + 7 == 7 + 0 == 7
• [] ++ [1,2,3] == [1,2,3] ++ [] == [1,2,3]
• {} 공용체 {apple} == {apple} 공용체 {} == {apple}

마지막으로 모노 이드는 연관성이 있어야합니다 . (객체의 왼쪽에서 오른쪽 순서를 변경하지 않는 한 원하는대로 긴 조합 문자열을 줄일 수 있습니다.) 추가는 괜찮습니다 ((5 + 3) +1 == 5+ (3+ 1)), 그러나 빼기는 ((5-3) -1! = 5- (3-1))이 아닙니다.

모나드

이제 특별한 종류의 세트와 객체를 결합하는 특별한 방법을 고려해 봅시다.

사물

세트에 특별한 종류의 객체 인 functions이 포함되어 있다고 가정 해 보겠습니다 . 그리고이 함수들은 흥미로운 시그니처를 가지고 있습니다. 그들은 숫자를 숫자로, 문자열을 문자열로 전달하지 않습니다. 대신 각 함수는 2 단계 프로세스로 숫자 목록에 숫자를 전달합니다.

1. 0 개 이상의 결과 계산
2. 그 결과를 어떻게 든 하나의 답으로 결합하십시오.

예 :

• 1-> [1] (입력을 감싸십시오)
• 1-> [] (입력을 버리고 목록에 아무것도 포함하지 않음)
• 1-> [2] (입력에 1을 더하고 결과를 래핑)
• 3-> [4, 6] (입력에 1을 더하고 입력에 2를 곱하고 여러 결과를 래핑 )

개체 결합

또한 기능을 결합하는 방법은 특별합니다. 함수를 결합하는 간단한 방법은 구성입니다 . 위의 예제를 사용하여 각 함수를 자체적으로 구성 해 보겠습니다.

• 1-> [1]-> [[1]] (입력 랩핑, 두 번)
• 1-> []-> [] (입력을 버리고 목록에서 아무것도 안함을 두 번 감 쌉니다)
• 1-> [2]-> [UH-OH! ] (목록에 "1을 추가"할 수 없습니다! ")
• 3-> [4, 6]-> [UH-OH! ] (목록에 1 개를 추가 할 수 없습니다!)

유형 이론을 너무 많이 이해하지 않고도 두 개의 정수를 결합하여 정수를 얻을 수 있지만 항상 두 개의 함수를 구성하고 동일한 유형의 함수를 얻을 수는 없습니다. (타입과 함수 A는 -> A는 구성되지만, A-는> [A]는 하지 않을 것이다.)

따라서 함수를 결합하는 다른 방법을 정의 해 봅시다. 이 두 함수를 결합 할 때 결과를 "이중 래핑"하고 싶지 않습니다.

다음은 우리가하는 일입니다. 두 함수 F와 G를 결합하려면 다음 프로세스를 따릅니다 ( binding 이라고 함 ) :

1. F에서 "결과"를 계산하지만 결합하지 마십시오.
2. G를 각 F의 결과에 개별적으로 적용한 결과를 계산하여 결과 모음을 생성합니다.
3. 2- 레벨 컬렉션을 평평하게하고 모든 결과를 결합합니다.

예제로 돌아가서,이 새로운 "바인딩"함수를 사용하여 함수를 자신과 결합 (바인딩) 해 보겠습니다.

• 1-> [1]-> [1] (입력 랩핑, 두 번)
• 1-> []-> [] (입력을 버리고 목록에서 아무것도 안함을 두 번 감 쌉니다)
• 1-> [2]-> [3] (1을 더한 다음 1을 다시 더하고 결과를 래핑합니다.)
• 3-> [4,6]-> [5,8,7,12] (입력에 1을 더하고 입력에 2를 곱하여 두 결과를 모두 유지 한 다음 두 결과에 모두 다시 수행 한 다음 최종 결과를 래핑합니다. 목록이 생성됩니다.)

함수를 결합하는 더 정교한 방법 은 연관 적입니다 (멋진 래핑 작업을 수행하지 않을 때 함수 구성이 연관되는 방식에 따름).

모든 것을 하나로 묶어

• 모나드는 함수 (결과)를 결합하는 방법을 정의하는 구조입니다.
• 모노 이드가 객체를 결합하는 방법을 정의하는 구조와 유사하게
• 조합 방법이 연관성 인 경우
• 어떤과 결합 될 수있는 특별한 '아니오 조합'이있는 곳 무언가 에 결과에 뭔가 변화가.

메모

결과를 "래핑"하는 방법에는 여러 가지가 있습니다. 목록이나 집합을 만들거나, 결과가 없는지 확인하면서 첫 번째 결과를 제외한 모든 결과를 버리고, 상태 사이드카를 첨부하고, 로그 메시지를 인쇄하는 등의 작업을 할 수 있습니다.

필자는 본질적인 아이디어를 직관적으로 전달하기 위해 정의를 약간 느슨하게 처리했습니다.

우리의 모나드가 a- > [a] 유형 의 함수에서 작동한다고 주장하여 약간 단순화했습니다 . 사실, 모나드는 a- > mb 유형 의 함수에서 작동 하지만 일반화는 주요 통찰력이 아닌 일종의 기술적 세부 사항입니다.

---

첫째, 우리가 사용할 확장과 라이브러리 :

{-# LANGUAGE RankNTypes, TypeOperators #-}

import Control.Monad (join)

이들 RankNTypes중 아래에 절대적으로 필수적인 유일한 것입니다. 나는 RankNTypes어떤 사람들이 유용하다고 생각 하는 것에 대한 설명을 썼 으므로 그것을 참조 할 것입니다.

Tom Crockett의 탁월한 답변을 인용 하면 다음과 같습니다.

모나드는 ...

• endofunctor, T : X-> X
• 자연스러운 변환, μ : T × T-> T , 여기서 × 는 펑터 구성을 의미합니다.
• 자연스러운 변환, η : I-> T , 여기서 I 는 X 의 정체성 엔도 펑터입니다.

... 다음 법률을 충족 :

• μ (μ (T × T) × T)) = μ (T × μ (T × T))
• μ (η (T)) = T = μ (T (η))

이것을 Haskell 코드로 어떻게 번역합니까? 자, 자연스러운 변형 의 개념부터 시작해 보겠습니다 .

-- | A natural transformations between two 'Functor' instances.  Law:
--
-- > fmap f . eta g == eta g . fmap f
--
-- Neat fact: the type system actually guarantees this law.
--
newtype f :-> g =
    Natural { eta :: forall x. f x -> g x }

형식의 유형은 f :-> g함수 유형과 유사하지만 두 유형 (종류 ) 간의 함수 로 생각하는 대신 두 펑터 (각 유형 ) 간의 모피 즘 으로 생각하십시오 . 예 :** -> *

listToMaybe :: [] :-> Maybe
listToMaybe = Natural go
    where go [] = Nothing
          go (x:_) = Just x

maybeToList :: Maybe :-> []
maybeToList = Natural go
    where go Nothing = []
          go (Just x) = [x]

reverse' :: [] :-> []
reverse' = Natural reverse

Basically, in Haskell, natural transformations are functions from some type f x to another type g x such that the x type variable is "inaccessible" to the caller. So for example, sort :: Ord a => [a] -> [a] cannot be made into a natural transformation, because it's "picky" about which types we may instantiate for a. One intuitive way I often use to think of this is the following:

• A functor is a way of operating on the content of something without touching the structure.
• A natural transformation is a way of operating on the structure of something without touching or looking at the content.

Now, with that out of the way, let's tackle the clauses of the definition.

The first clause is "an endofunctor, T : X -> X." Well, every Functor in Haskell is an endofunctor in what people call "the Hask category," whose objects are Haskell types (of kind *) and whose morphisms are Haskell functions. This sounds like a complicated statement, but it's actually a very trivial one. All it means is that that a Functor f :: * -> * gives you the means of constructing a type f a :: * for any a :: * and a function fmap f :: f a -> f b out of any f :: a -> b, and that these obey the functor laws.

Second clause: the Identity functor in Haskell (which comes with the Platform, so you can just import it) is defined this way:

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    fmap f (Identity a) = Identity (f a)

So the natural transformation η : I -> T from Tom Crockett's definition can be written this way for any Monad instance t:

return' :: Monad t => Identity :-> t
return' = Natural (return . runIdentity)

Third clause: The composition of two functors in Haskell can be defined this way (which also comes with the Platform):

newtype Compose f g a = Compose { getCompose :: f (g a) }

-- | The composition of two 'Functor's is also a 'Functor'.
instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose fga) = Compose (fmap (fmap f) fga)

So the natural transformation μ : T × T -> T from Tom Crockett's definition can be written like this:

join' :: Monad t => Compose t t :-> t
join' = Natural (join . getCompose)

The statement that this is a monoid in the category of endofunctors then means that Compose (partially applied to just its first two parameters) is associative, and that Identity is its identity element. I.e., that the following isomorphisms hold:

• Compose f (Compose g h) ~= Compose (Compose f g) h
• Compose f Identity ~= f
• Compose Identity g ~= g

These are very easy to prove because Compose and Identity are both defined as newtype, and the Haskell Reports define the semantics of newtype as an isomorphism between the type being defined and the type of the argument to the newtype's data constructor. So for example, let's prove Compose f Identity ~= f:

Compose f Identity a
    ~= f (Identity a)                 -- newtype Compose f g a = Compose (f (g a))
    ~= f a                            -- newtype Identity a = Identity a
Q.E.D.

---

Note: No, this isn't true. At some point there was a comment on this answer from Dan Piponi himself saying that the cause and effect here was exactly the opposite, that he wrote his article in response to James Iry's quip. But it seems to have been removed, perhaps by some compulsive tidier.

Below is my original answer.

---

It's quite possible that Iry had read From Monoids to Monads, a post in which Dan Piponi (sigfpe) derives monads from monoids in Haskell, with much discussion of category theory and explicit mention of "the category of endofunctors on Hask" . In any case, anyone who wonders what it means for a monad to be a monoid in the category of endofunctors might benefit from reading this derivation.

---

I came to this post by way of better understanding the inference of the infamous quote from Mac Lane's Category Theory For the Working Mathematician.

In describing what something is, it's often equally useful to describe what it's not.

The fact that Mac Lane uses the description to describe a Monad, one might imply that it describes something unique to monads. Bear with me. To develop a broader understanding of the statement, I believe it needs to be made clear that he is not describing something that is unique to monads; the statement equally describes Applicative and Arrows among others. For the same reason we can have two monoids on Int (Sum and Product), we can have several monoids on X in the category of endofunctors. But there is even more to the similarities.

Both Monad and Applicative meet the criteria:

• endo => any arrow, or morphism that starts and ends in the same place
• functor => any arrow, or morphism between two Categories

  (e.g., in day to day Tree a -> List b, but in Category Tree -> List)

• monoid => single object; i.e., a single type, but in this context, only in regards to the external layer; so, we can't have Tree -> List, only List -> List.

The statement uses "Category of..." This defines the scope of the statement. As an example, the Functor Category describes the scope of f * -> g *, i.e., Any functor -> Any functor, e.g., Tree * -> List * or Tree * -> Tree *.

What a Categorical statement does not specify describes where anything and everything is permitted.

In this case, inside the functors, * -> * aka a -> b is not specified which means Anything -> Anything including Anything else. As my imagination jumps to Int -> String, it also includes Integer -> Maybe Int, or even Maybe Double -> Either String Int where a :: Maybe Double; b :: Either String Int.

So the statement comes together as follows:

• functor scope :: f a -> g b (i.e., any parameterized type to any parameterized type)
• endo + functor :: f a -> f b (i.e., any one parameterized type to the same parameterized type) ... said differently,
• a monoid in the category of endofunctor

So, where is the power of this construct? To appreciate the full dynamics, I needed to see that the typical drawings of a monoid (single object with what looks like an identity arrow, :: single object -> single object), fails to illustrate that I'm permitted to use an arrow parameterized with any number of monoid values, from the one type object permitted in Monoid. The endo, ~ identity arrow definition of equivalence ignores the functor's type value and both the type and value of the most inner, "payload" layer. Thus, equivalence returns true in any situation where the functorial types match (e.g., Nothing -> Just * -> Nothing is equivalent to Just * -> Just * -> Just * because they are both Maybe -> Maybe -> Maybe).

Sidebar: ~ outside is conceptual, but is the left most symbol in f a. It also describes what "Haskell" reads-in first (big picture); so Type is "outside" in relation to a Type Value. The relationship between layers (a chain of references) in programming is not easy to relate in Category. The Category of Set is used to describe Types (Int, Strings, Maybe Int etc.) which includes the Category of Functor (parameterized Types). The reference chain: Functor Type, Functor values (elements of that Functor's set, e.g., Nothing, Just), and in turn, everything else each functor value points to. In Category the relationship is described differently, e.g., return :: a -> m a is considered a natural transformation from one Functor to another Functor, different from anything mentioned thus far.

Back to the main thread, all in all, for any defined tensor product and a neutral value, the statement ends up describing an amazingly powerful computational construct born from its paradoxical structure:

• on the outside it appears as a single object (e.g., :: List); static
• but inside, permits a lot of dynamics
  • any number of values of the same type (e.g., Empty | ~NonEmpty) as fodder to functions of any arity. The tensor product will reduce any number of inputs to a single value... for the external layer (~fold that says nothing about the payload)
  • infinite range of both the type and values for the inner most layer

In Haskell, clarifying the applicability of the statement is important. The power and versatility of this construct, has absolutely nothing to do with a monad per se. In other words, the construct does not rely on what makes a monad unique.

When trying to figure out whether to build code with a shared context to support computations that depend on each other, versus computations that can be run in parallel, this infamous statement, with as much as it describes, is not a contrast between the choice of Applicative, Arrows and Monads, but rather is a description of how much they are the same. For the decision at hand, the statement is moot.

This is often misunderstood. The statement goes on to describe join :: m (m a) -> m a as the tensor product for the monoidal endofunctor. However, it does not articulate how, in the context of this statement, (<*>) could also have also been chosen. It truly is a an example of six/half dozen. The logic for combining values are exactly alike; same input generates the same output from each (unlike the Sum and Product monoids for Int because they generate different results when combining Ints).

So, to recap: A monoid in the category of endofunctors describes:

   ~t :: m * -> m * -> m *
   and a neutral value for m *

(<*>) and (>>=) both provide simultaneous access to the two m values in order to compute the the single return value. The logic used to compute the return value is exactly the same. If it were not for the different shapes of the functions they parameterize (f :: a -> b versus k :: a -> m b) and the position of the parameter with the same return type of the computation (i.e., a -> b -> b versus b -> a -> b for each respectively), I suspect we could have parameterized the monoidal logic, the tensor product, for reuse in both definitions. As an exercise to make the point, try and implement ~t, and you end up with (<*>) and (>>=) depending on how you decide to define it forall a b.

If my last point is at minimum conceptually true, it then explains the precise, and only computational difference between Applicative and Monad: the functions they parameterize. In other words, the difference is external to the implementation of these type classes.

In conclusion, in my own experience, Mac Lane's infamous quote provided a great "goto" meme, a guidepost for me to reference while navigating my way through Category to better understand the idioms used in Haskell. It succeeds at capturing the scope of a powerful computing capacity made wonderfully accessible in Haskell.

However, there is irony in how I first misunderstood the statement's applicability outside of the monad, and what I hope conveyed here. Everything that it describes turns out to be what is similar between Applicative and Monads (and Arrows among others). What it doesn't say is precisely the small but useful distinction between them.

- E

---

The answers here do an excellent job in defining both monoids and monads, however, they still don't seem to answer the question:

And on a less important note, is this true and if so could you give an explanation (hopefully one that can be understood by someone who doesn't have much Haskell experience)?

The crux of the matter that is missing here, is the different notion of "monoid", the so-called categorification more precisely -- the one of monoid in a monoidal category. Sadly Mac Lane's book itself makes it very confusing:

All told, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor.

Main confusion

Why is this confusing? Because it does not define what is "monoid in the category of endofunctors" of X. Instead, this sentence suggests taking a monoid inside the set of all endofunctors together with the functor composition as binary operation and the identity functor as a monoidal unit. Which works perfectly fine and turns into a monoid any subset of endofunctors that contains the identity functor and is closed under functor composition.

Yet this is not the correct interpretation, which the book fails to make clear at that stage. A Monad f is a fixed endofunctor, not a subset of endofunctors closed under composition. A common construction is to use f to generate a monoid by taking the set of all k-fold compositions f^k = f(f(...)) of f with itself, including k=0 that corresponds to the identity f^0 = id. And now the set S of all these powers for all k>=0 is indeed a monoid "with product × replaced by composition of endofunctors and unit set by the identity endofunctor".

And yet:

• This monoid S can be defined for any functor f or even literally for any self-map of X. It is the monoid generated by f.
• The monoidal structure of S given by the functor composition and the identity functor has nothing do with f being or not being a monad.

And to make things more confusing, the definition of "monoid in monoidal category" comes later in the book as you can see from the table of contents. And yet understanding this notion is absolutely critical to understanding the connection with monads.

(Strict) monoidal categories

Going to Chapter VII on Monoids (which comes later than Chapter VI on Monads), we find the definition of the so-called strict monoidal category as triple (B, *, e), where B is a category, *: B x B-> B a bifunctor (functor with respect to each component with other component fixed) and e is a unit object in B, satisfying the associativity and unit laws:

(a * b) * c = a * (b * c)
a * e = e * a = a

for any objects a,b,c of B, and the same identities for any morphisms a,b,c with e replaced by id_e, the identity morphism of e. It is now instructive to observe that in our case of interest, where B is the category of endofunctors of X with natural transformations as morphisms, * the functor composition and e the identity functor, all these laws are satisfied, as can be directly verified.

What comes after in the book is the definition of the "relaxed" monoidal category, where the laws only hold modulo some fixed natural transformations satisfying so-called coherence relations, which is however not important for our cases of the endofunctor categories.

Monoids in monoidal categories

Finally, in section 3 "Monoids" of Chapter VII, the actual definition is given:

A monoid c in a monoidal category (B, *, e) is an object of B with two arrows (morphisms)

mu: c * c -> c
nu: e -> c

making 3 diagrams commutative. Recall that in our case, these are morphisms in the category of endofunctors, which are natural transformations corresponding to precisely join and return for a monad. The connection becomes even clearer when we make the composition * more explicit, replacing c * c by c^2, where c is our monad.

Finally, notice that the 3 commutative diagrams (in the definition of a monoid in monoidal category) are written for general (non-strict) monoidal categories, while in our case all natural transformations arising as part of the monoidal category are actually identities. That will make the diagrams exactly the same as the ones in the definition of a monad, making the correspondence complete.

Conclusion

In summary, any monad is by definition an endofunctor, hence an object in the category of endofunctors, where the monadic join and return operators satisfy the definition of a monoid in that particular (strict) monoidal category. Vice versa, any monoid in the monoidal category of endofunctors is by definition a triple (c, mu, nu) consisting of an object and two arrows, e.g. natural transformations in our case, satisfying the same laws as a monad.

Finally, note the key difference between the (classical) monoids and the more general monoids in monoidal categories. The two arrows mu and nu above are not anymore a binary operation and a unit in a set. Instead, you have one fixed endofunctor c. The functor composition * and the identity functor alone do not provide the complete structure needed for the monad, despite that confusing remark in the book.

Another approach would be to compare with the standard monoid C of all self-maps of a set A, where the binary operation is the composition, that can be seen to map the standard cartesian product C x C into C. Passing to the categorified monoid, we are replacing the cartesian product x with the functor composition *, and the binary operation gets replaced with the natural transformation mu from c * c to c, that is a collection of the join operators

join: c(c(T))->c(T)

for every object T (type in programming). And the identity elements in classical monoids, which can be identified with images of maps from a fixed one-point-set, get replaced with the collection of the return operators

return: T->c(T) 

But now there are no more cartesian products, so no pairs of elements and thus no binary operations.

참고URL : https://stackoverflow.com/questions/3870088/a-monad-is-just-a-monoid-in-the-category-of-endofunctors-whats-the-problem