모노 이드 동형은 정확히 무엇입니까?

모노 이드 동형은 정확히 무엇입니까?

---

Monoid Morphisms, Products 및 Coproducts 에서 monoid homomorphism에 대해 읽었으며 100 % 이해할 수 없었습니다.

저자는 다음과 같이 말합니다 (원본 강조) :

이 length함수 는 모노 이드 구조를 유지하면서 에서 String로 매핑됩니다 . 이러한 보존 방식으로 하나의 monoid에서 다른 monoid로 매핑되는 이러한 기능을 monoid homomorphism 이라고합니다 . 일반적으로 모노 이드 및 , 동형 및 모든 값 , 의 경우 다음 방정식이 유지됩니다.Int MNf: M => Nx:My:M

f(x |+| y) == (f(x) |+| f(y))

f(mzero[M]) == mzero[N]

그는 데이터 유형 String과 Int모노 이드이고, 모노 이드 구조를 보존하는 함수 length맵 String => Int( Int모노 이드)이기 때문에 모노 이드 동형이라고 부릅니다.

---

그는 데이터 유형 String 및 Int가 모노 이드라는 것을 의미합니까?

아니 , 모노 이드 도 String아닙니다 Int. 모노 이드는 3 튜플 (S, ⊕, e) 이고 , 여기서 ⊕는 이항 연산자입니다. ⊕ : SxS → S , 모든 원소 a, b, c∈S에 대해 (a⊕b) ⊕c = a⊕ (b⊕c) 이고 e∈S 는 a⊕e = e⊕a = a 와 같은 "식별 요소" 입니다. String및 Int유형, 그래서 기본적으로 값 세트가 아닌 3 튜플이다.

기사 내용 :

String연결 과 Int덧셈 을 관계가있는 모노 이드의 예로 들어 봅시다 .

따라서 저자는 이항 연산자 ( (++)의 경우 String및 (+)의 경우 Int) 도 명확하게 언급합니다 . 신원 (의 경우 빈 문자열 String과 0의 경우는 Int) 암시 남아 있습니다; 독자를위한 연습으로 정체성을 남겨 두는 것은 비공식적 인 영어 담화에서 일반적입니다.

이제 우리가 두 개의 모노 이드 구조 (M, ⊕, e _m ) 와 (N, ⊗, e _n ) 을 가지고 있다고 가정하면, 함수 f : M → N (like length)은 f를 보유하고 있는 monoid homomorphism [wiki] 이라고합니다. (m ₁ ⊕m ₂ ) = f (m ₁ ) ⊗f (m ₂ ) 모든 요소 m ₁ , m ₂ ∈M 및 해당 매핑도 동일 요소 f (e _m ) = e _{n을 유지} 합니다.

예를 들어 length :: String -> Int우리가 monoids 고려할 수 때문에, 모노 이드의 이체 동형이다 ( String, (++), "") 와 ( Int, (+), 0) . 그것은 다음을 보유합니다.

1. length (s1 ++ s2) == length s1 + length s2(모든 Strings s1및 s2); 과
2. length "" == 0.

---

데이터 유형은 자체적으로 monoid가 될 수 없습니다. monoid의 경우 데이터 유형 T과 두 가지가 더 필요합니다 .

• 연관 이항 연산은 , 현실을 부르 자 |+|, 그 형의 두 가지 요소를 소요 T및 유형의 요소를 생산T
• 타입 의 아이덴티티 요소 를 T호출 해 봅시다. 타입 의 i모든 요소 t에 T대해 다음이 유지됩니다.t |+| i = i |+| t = t

다음은 monoid의 몇 가지 예입니다.

• 연산 = 더하기 및 ID = 0 인 정수 세트
• 연산 = 곱셈 및 동일성 = 1 인 정수 세트
• 작업이있는 목록 세트 = 추가 및 ID = 빈 목록
• 작업 = 연결 및 ID = 빈 문자열이있는 문자열 세트

모노 이드 동형

문자열 연결 모노 이드는 .length모든 요소 에 적용 하여 정수 더하기 모노 이드로 변환 할 수 있습니다 . 이 두 세트는 모두 모노 이드를 형성합니다. 그건 그렇고, 우리는 "정수 세트가 모노 이드를 형성한다"라고 말할 수 없다는 것을 기억하십시오. 우리는 연관 연산과 그에 상응하는 신원 요소를 선택해야합니다. 예를 들어 나눗셈을 연산으로 취하면 첫 번째 규칙을 위반합니다 (정수 유형의 요소를 생성하는 대신 float / double 유형의 요소를 생성 할 수 있음).

메서드를 length사용하면 monoid (문자열 연결)에서 다른 monoid (정수 더하기)로 이동할 수 있습니다. 이러한 작업이 모노 이드 구조도 유지하는 경우 모노 이드 동형으로 간주됩니다 .

구조를 보존한다는 것은 다음을 의미합니다.

length(t1 |+| t2) = length(t1) |+| length(t2)

and

length(i) = i'

여기서, t1및 t2"소스"모노 이드 요소를 나타내고, i"소스"모노 이드의 신원이고, i'"대상"모노 이드의 ID이다. 직접 시도해보고 length실제로 문자열 연결 모노 이드에 대한 구조 보존 작업 임을 확인할 수 있지만 예 indexOf("a")는 그렇지 않습니다.

모노 이드 동형

As demonstrated, length maps all strings to their corresponding integers and forms a monoid with addition as operation and zero as identity. But we can't go back - for every string, we can figure out its length, but given a length we can't reconstruct the "original" string. If we could, then the operation of "going forward" combined with the operation of "going back" would form a monoid isomorphism.

Isomorphism means being able to go back and forth without any loss of information. For example, as stated earlier, list forms a monoid under appending as operation and empty list as identity element. We could go from "list under appending" monoid to "vector under appending" monoid and back without any loss of information, which means that operations .toVector and .toList together form an isomorphism. Another example of an isomorphism, which Runar mentioned in his text, is String ⟷ List[Char].

---

Colloquially a homomorphism is a function that preserves structure. In the example of the length function the preserved structure is the sum of the lengths of to strings being equal to the length of the concatenation of the same strings. Since both strings and integers can be regarded as monoids (when equipped with an identity and an associative binary operation obeying the monoid laws) length is called a monoid homomorphism.

See also the other answers for a more technical explanation.

참고URL : https://stackoverflow.com/questions/55993254/what-is-monoid-homomorphism-exactly