Monoid_Haskell 노트 9

一.幺元

수학 세계에서, 0 은 가법 단위원, 1 은 승법 단위원 (identity element) 입니다. 예를 들어:

> 0 + 3
3
> 3 + 0
3
> 1 * 3
3
> 3 * 1
3

양자의 공통점은 연산에 참여하지만, 다른 한 쪽의 조작수를 변경하지 않는 것입니다:

In mathematics, an identity element or neutral element is a special type of element of a set with respect to a binary operation on that set, which leaves other elements unchanged when combined with them.

(Identity element 에서 인용)

단위원은 집합 내의 이항 연산으로 정의되며, 단위원과 결합하여 연산할 때, 다른 요소는 불변입니다 (연산 결과는 여전히 해당 요소). 좌단위원 (e * a = a) 과 우단위원 (a * e = a) 으로 세분되며, 동시에 만족하면 단위원이라고 하며, 幺元이라고도 합니다 (이산 수학에서 이를 배웠습니다)

Haskell 에도 유사한 것이 있습니다 (Monoid 라고 불림). 예를 들어 ++ 연산이 [] 를 만날 경우:

> [] ++ "abc"
"abc"
> "abc" ++ []
"abc"

++ 는 List 위에서 정의된 이항 연산이며, [] 는 幺元의 성질에 부합합니다

二.Monoid

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

(Monoid 에서 인용)

모노이드 (monoid) 는 추상대수학 중의 개념으로, 결합 가능한 이항 연산과 幺元을 갖는 대수 구조를 가리킵니다. 정규 (엄밀) 한 기술은 다음과 같습니다:

모노이드는 이항 연산 *: M × M → M 을 갖는 집합 M 으로,以下の 공리에 부합합니다: 결합률: M 내의 임의의 a, b, c 에 대해, (a*b)*c = a*(b*c) 幺元: M 내의 요소 e 가 존재하며, M 내의 임의의 a 가 a*e = e*a = a 에 부합

(幺半群 에서 인용)

결합률에 따르는 이항 함수와, 그 함수의 幺元이 되는 값의 2 개로 Monoid 를 구성합니다

Monoid typeclass

Data.Monoid 모듈에 위치:

class Semigroup a => Monoid a where
    mempty  :: a
    mappend :: a -> a -> a
    mappend = (<>)
    mconcat :: [a] -> a
    mconcat = foldr mappend mempty

(GHC.Base 에서 인용)

P.S. 주의, (<>) 는 Semigroup 클래스에서 정의되며, mappend = (<>) 는 mappend 와 <> 가 완전히 동등함을 선언

Monoid(모노이드) 는 먼저 Semigroup(반군, 상세는 마지막 부분을 참조) 여야 합니다. 그 중에서 mempty 는 幺元, mappend 는 그 이항 함수입니다

mappend 는 모노이드의 정의에서 요구되는 결합률에 따르는 이항 함수로, 이름이 그다지 적절하지 않습니다(append 를 포함하고 있지만, append 에 유사한 동작을 구현할 필요는 없습니다). 2 개의 monoid 값을 받아, 다른 monoid 값을 반환합니다

mconcat 은 monoid 값의 리스트를 받아, mappend 로 접기 (fold, 또는 reduce 규약) 하여 1 개의 monoid 값으로 합니다. 디폴트 구현이 주어지며, 일반적으로 자신이 구현할 필요는 없습니다. 더 적절한 구현 방식 (예를 들어 효율이 높은 방식) 이 있는 경우를 제외

Monoid laws

Monoid 클래스도 몇 가지 규칙을 따라야 합니다. 다음과 같습니다:

mempty `mappend` x = x
x `mappend` mempty = x
(x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)

전 2 조는 mempty 가 幺元임을 보증하며, 제 3 조는 이항 함수 mappend 가 결합률을 만족함을 설명

三.Monoid instances

List

instance Semigroup [a] where
  (<>) = (++)

instance Monoid [a] where
  mempty  = []
  mconcat xss = [x | xs <- xss, x <- xs]

(GHC.Base 에서 인용)

우리가 생각한 대로, List 및 List 위에서 정의된 ++ 연산과 空 List 幺元으로, 모노이드를 구성합니다

Monoid laws 로 검증해 봅시다:

> mempty `mappend` "hoho"
"hoho"
> "hoho" `mappend` mempty
"hoho"
> "a" `mappend` "b" `mappend` "c"
"abc"
> "a" `mappend` ("b" `mappend` "c")
"abc"

mempty 는 幺元이며, mappend 도 결합률을 만족하므로, List 는 합격의 Monoid 인스턴스입니다

P.S. mempty 가 구체적으로 무엇인지 알고 싶은 경우, 이렇게 합니다:

> mempty :: [a]
[]
> mempty :: Ordering
EQ
> mempty :: ()
()

주의, mempty 에 구체적인 타입 (예를 들어 [a] 또는 [Int] :: *, [] :: * -> * 은 아님) 을 지정해야 합니다

Product 와 Sum

冒頭の 幺元 부분에서 가법 단위원과 승법 단위원에 언급했습니다. 동시에 그것들도 결합률을 만족하므로, 수치 연산에는 2 개의 모노이드가 존재합니다. 각각 가법과 幺元 0, 및 승법과 幺元 1 입니다

다시 말해, Num 에는 2 종류의 다른 Monoid 구현이 존재할 수 있습니다. 각각 이항 함수 + 와 幺元 0, 및 이항 함수 * 와 幺元 1 입니다. 또 이 종류의 씬에 직면했으므로, ZipList 를 만든 것처럼, Sum 과 Product 클래스를 만들었습니다 (Data.Monoid 에 위치):

newtype Product a = Product { getProduct :: a }
  deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)
newtype Sum a = Sum { getSum :: a }
    deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)

P.S. ZipList 와 newtype 의 과거에 대해서는, [newtype_Haskell 노트 8](/articles/newtype-haskell 노트 8/) 참조

Product 의 Monoid 구현은 다음과 같습니다:

instance Num a => Semigroup (Product a) where
  (<>) = coerce ((*) :: a -> a -> a)

instance Num a => Monoid (Product a) where
  mempty = Product 1

幺元은 Product 1, 이항 함수는 coerce ((*) :: a -> a -> a) 입니다. 그 중에서 coerce 는 타입 변환에 사용됩니다 (상세는 Data.Coerce 참조). 이하에 상당:

Product x `mappend` Product y = Product (x * y)

Num 위에서 정의되었으므로, 幺元의 값은 구체적인 타입과 관계가 있습니다:

> getProduct (mempty :: (Product Int))
1
> getProduct (mempty :: (Product Double))
1.0

Sum 의 구현은 Product 와 유사:

instance Num a => Semigroup (Sum a) where
  (<>) = coerce ((+) :: a -> a -> a)

instance Num a => Monoid (Sum a) where
  mempty = Sum 0

試玩해 봅시다:

> getSum $ Sum 3 `mappend` (mconcat $ map Sum [1, 2, 3])
9

Any 와 All

Num 과 유사로, Bool 값에도 2 개의 모노이드가 존재: || 연산과 幺元 False, && 연산과 幺元 True:

-- ||연산과 幺元 False
newtype Any = Any { getAny :: Bool }
  deriving (Eq, Ord, Read, Show, Bounded, Generic)

instance Semigroup Any where
  (<>) = coerce (||)

instance Monoid Any where
  mempty = Any False

-- &&연산과 幺元 True
newtype All = All { getAll :: Bool }
  deriving (Eq, Ord, Read, Show, Bounded, Generic)

instance Semigroup All where
  (<>) = coerce (&&)

instance Monoid All where
  mempty = All True

Any 와 All 도 마찬가지로 Data.Monoid 에 위치

Ordering

Ordering 타입 정의는 매우 간단:

data Ordering = LT | EQ | GT

대응하는 Monoid 구현은 다음과 같습니다:

instance Semigroup Ordering where
  LT <> _ = LT
  EQ <> y = y
  GT <> _ = GT

instance Monoid Ordering where
  mempty             = EQ

P.S. 앞에서 언급한其它 Monoid instances 와 달리, 여기의 mappend 는 신규 작성으로, 기존 함수를 직접 사용한 것은 아닙니다 (이전은 기존 함수로 검증하여, 모노이드 특성이 있는지 확인)

이 함수의 동작은, 연산 결과는 왼쪽의 조작수를 취하지만, 왼쪽이 EQ 인 경우를 제외합니다 (此时는 오른쪽을 취함). 조금 이상하게 보이지만, 문자열 (사전순) 비교로 이해할 수 있습니다. 예를 들어 compare "ab" "am" 의 비교 결과는 LT, LT <> _ = LT 는 현재의 비교 결과가 LT 인 경우, 계속 뒤를 비교해도 결과는 여전히 LT 임을 의미. 예를 들어 compare "absolute" "america". 유사로, EQ <> y = y 는 현재의 결과가 EQ 인 경우, 나머지 부분의 비교 결과가 최종 결과임을 나타내며, GT <> _ = GT 는 현재의 결과가 GT 인 경우,後面이 무엇이든, 최종 결과는 반드시 GT 임을 나타

Maybe

instance Semigroup a => Semigroup (Maybe a) where
  Nothing <> b       = b
  a       <> Nothing = a
  Just a  <> Just b  = Just (a <> b)

instance Semigroup a => Monoid (Maybe a) where
  mempty = Nothing

P.S. 주의 여기의 타입 제약으로, a 가 Semigroup 임을 요구. Just a <> Just b = Just (a <> b) 가 정상적으로 연산할 수 있음을 보증하기 위함

따라서, Maybe 의 幺元은 Nothing, 연산도 신규 작성이지만, 비교적 교묘하며, 2 개의 Just a 의 연산 결과는 내용에 대해 연산하고, 다시 Just 에装入. 따라서 내용도 이 종류의 연산 (<>) 을 서포트해야 합니다. 예를 들어:

> Just (Sum 2) `mappend` Just (Sum 3)
Just (Sum {getSum = 5})
> Just [1, 2] `mappend` Just [3, 4]
Just [1,2,3,4]

내용이 <> 연산을 서포트하지 않는 경우, Maybe 의 연산을 수행할 수 없습니다:

> Just 2 `mappend` Just (3 :: Int)

<interactive>:195:1: error:
    ? No instance for (Monoid Int) arising from a use of 'mappend'

四.Foldable 와 Monoid

Monoid 인스턴스는 모두 mappend 동작을 서포트하며, "겹쳐쌓기"로 이해할 수 있습니다. 2 개의 Monoid 인스턴스를 연산을 통해 1 개의 Monoid 인스턴스로 합니다. 또한, "접기"(mconcat) 도 서포트합니다. 한 조의 Monoid 인스턴스를 머리부터 꼬리까지 "겹쳐쌓아",从而 "접어" 1 개의 Monoid 인스턴스로 할 수 있습니다

한 조의 것이 "접어" 1 개의 것이 될 수 있으면, 이 것은 "접기 가능", 즉 Foldable:

class Foldable t where
  {-# MINIMAL foldMap | foldr #-}
  foldMap :: Monoid m => (a -> m) -> t a -> m
  foldr :: (a -> b -> b) -> b -> t a -> b

(Data.Foldable 에서 인용)

P.S. Foldable 은 Data.Foldable 모듈에 위치. 함수명은 Prelude 중의 List 함수명과 충돌하므로, 일반적으로 별명을 통해 도입. 예를 들어:

import qualified Data.Foldable as Foldable

class 정의에 따르면, foldMap 또는 foldr 을 구현하기만 하면 Foldable 인스턴스가 될 수 있습니다. 타입 선언에서 보면, foldMap 은 분명히 Monoid 面向이며, foldr 은 더 일반적인 fold 인터페이스

구체적으로 보면, foldMap 이 수행하는 것은 함수 a -> m 로 Foldable 구조 (t a) 를 매핑하여, 내용이 한 조의 Monoid 로 조성된 Foldable 구조를 얻고, 다시 mconcat(또는 mappend) 를 통해 이 한 조의 Monoid 를 접어 1 개의 Monoid 로 하여 반환

실제 응용

Foldable 을 구현하는 실제적인 의의는 무엇일까요? 예를 봅시다:

module BTree
( Tree(..)
, singleton
, add
, fromList
) where

import Data.Monoid
import Data.Foldable

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

singleton x = Node x EmptyTree EmptyTree

add x EmptyTree = singleton x
add x (Node a left right)
  | x == a = Node a left right
  | x > a = Node a left (add x right)
  | x < a = Node a (add x left) right

fromList xs = foldr add EmptyTree xs

이것은 커스터마이즈한 이진수 타입 (실제로는 이진검색수로, 가장 단순폭포한 것. 일단 이진수로 사용). 기본적인 이진수 구축 기능 (singleton, add 와 fromList) 을 가지며,それに Monoid 인터페이스를 구현:

instance Monoid a =>  Monoid (Tree a) where
  mempty = EmptyTree
  a `mappend` EmptyTree = a
  EmptyTree `mappend` b = b
  (Node x xl xr) `mappend` (Node y yl yr) = Node (x `mappend` y) (xl `mappend` yl) (xr `mappend` yr)

주의, Tree a 의 a 도 Monoid 인스턴스임을 요구. Node 의 내용에 대해 mappend 를 수행할 필요가 있기 때문. 앞에서 언급한 Maybe 의 Monoid 구현과 유사

Monoid laws 를 시:

> let nodeA = Node (Sum 1) (singleton (Sum 2)) EmptyTree
> let nodeB = Node 5 (Node 3 (singleton 1) (singleton 6)) (Node 9 (singleton 8) (singleton 10))
> let nodeC = singleton (Sum 6)
> nodeA `mappend` nodeB `mappend` nodeC
Node (Sum {getSum = 12}) (Node (Sum {getSum = 5}) (Node (Sum {getSum = 1}) EmptyTree EmptyTree) (Node (Sum {getSum = 6}) EmptyTree EmptyTree)) (Node (Sum {getSum = 9}) (Node (Sum {getSum = 8}) EmptyTree EmptyTree) (Node (Sum {getSum = 10}) EmptyTree EmptyTree))
> nodeA `mappend` (nodeB `mappend` nodeC)
Node (Sum {getSum = 12}) (Node (Sum {getSum = 5}) (Node (Sum {getSum = 1}) EmptyTree EmptyTree) (Node (Sum {getSum = 6}) EmptyTree EmptyTree)) (Node (Sum {getSum = 9}) (Node (Sum {getSum = 8}) EmptyTree EmptyTree) (Node (Sum {getSum = 10}) EmptyTree EmptyTree))

3 그루의 나무의 구조는 다음과 같습니다:

-- nodeA
1
  2
  空
-- nodeB
5
  3
    1
    6
  9
    8
    10
-- nodeC
6

mappend 결과:

12
  5
    1
    6
  9
    8
    10

실제로는 대응 위치에서 구화. 空 노드가 0 의 역할을 함. 생각, 우리가 어떻게 "구화"라는 의도를 표현했는가?

"구화"는 Sum 이라는 Monoid 인스턴스를 통해 표현. Tree 는 단순한 구조. 수치가 먼저 Sum 으로 1 층 싸여, 구화의 시맨틱스를添え, 다시 Tree 에填入. 나무의 구조 의미를 가짐. 好像，有那么点意思了

계속, Foldable 인터페이스를 구현. Foldable 와 Monoid 의 관계가 친밀한 것을 기억하면,一类의 Monoid 인스턴스를 foldable 로 하는 것은 용이:

instance Foldable.Foldable Tree where
  foldMap f EmptyTree = mempty
  foldMap f (Node x l r) = Foldable.foldMap f l `mappend`
                              f x `mappend`
                              Foldable.foldMap f r

大招 축력 완료. 먼저起手式:

let tree = fromList [7, 3, 1, 2, 6, 9, 8, 5]
> getAny $ Foldable.foldMap (\x -> Any $ x == 3) tree
True

이러한 나무를 작성:

-- tree
5
  2
    1
    3
  8
    6
      空
      7
    9

한 마디로 포함성 판단을 완성: getAny $ Foldable.foldMap (\x -> Any $ x == 3) tree. 출초가 너무 빨라看清えない? 슬로우 모션으로 분해:

0. 매핑 함수 (\x -> Any $ x == 3) 가 입력값과 3 의 상등성을 비교하여, 비교 결과를 Any 에装入

1. 바닥에서 위로 tree 를 트래버스. 매핑 함수로 각 노드상의 수치를 변환. 空 노드에 조우하면 mempty 에 싸, Monoid 나무 (Any 나무) 를 형성

2. Any 나무를 접기. 구체적으로는 바닥에서 위로 "左 mappend 中 mappend 右" 연산을 수행. Any 의 mappend 는 값에 대해 또는 연산 (||). mempty 에 조우하면 Any False 에 대응. 나무根에走到時, 연산 결과는 Any True

3. getAny 로 접기 결과 True 를取出

P.S. 주의, Any 나무를 생성과 트래버스 접기는 1 회의 트래버스 중에서 동시에 수행되며, 2 회 트래버스하는 것은 아닙니다 (1 회차는 매핑, 2 회차는 접기). 위에서拆开て 보는 것은 이해하기 쉽기 때문

起手式 후, 大招 가 왔다:

> Foldable.foldMap (\x -> [x]) tree
[1,2,3,5,6,7,8,9]

待, 무슨 일이 발생?

한 마디로 나무를 배열로 변환. 게다가, 몰래 정렬도 했다.好吧, 조금 과장. 정렬은 이진검색수가 수행 (fromList ��� 때 add 로建树). 따라서 나무를 배열로 변환했을 뿐. 구체:

0. 매핑 함수 (\x -> [x]) 가 입력의 값을 List 에装入 (수집)

1. 바닥에서 위로 tree 를 트래버스. 매핑 함수로 각 노드상의 수치를 변환. 空 노드에 조우하면 mempty 에 싸, List 나무를 형성

2. List 나무를 접기. 구체적으로는 바닥에서 위로 "左 mappend 中 mappend 右" 연산을 수행. List 의 mappend 는 접속 (++). mempty 에 조우하면 [] 에 대응. 나무根에走到時, 연산 결과는 [나무상 모든 요소]

3. 직접 접기 결과를 출력. [나무상 모든 요소]

한 마디로 포함성 판단을 완성. 한 마디로 나무상 요소 수집을 완성. 매우驚艶한 조작

P.S. 나무에 대해 구화, 구적, 요소 필터링은? 매우 용이:

> getSum $ Foldable.foldMap Sum tree
41
> getProduct $ Foldable.foldMap Product tree
90720
> Foldable.foldMap (\x -> if x > 5 then [x] else []) tree
[6,7,8,9]

五.군, 반군과 모노이드

수학적 의미에서 보면, 모두집합과 이항 연산으로 형성된 대수 구조:

• 반군: 집합 S 및 그 위의 이항 연산 ·:S×S→S. · 가 결합률을 만족하는 경우, 즉: ?x,y,z∈S, (x·y)·z=x·(y·z) 가 있으면, 有序對 (S,·) 를 반군이라고 함

• 모노이드: 집합 M 및 그 위의 이항 연산 *: M × M → M. 해당 연산은 결합률을 만족하며, 幺元도 집합里에 있음

• 군: 군은 집합 G 로, 연산 · 와 함께. 임의의 2 개의 요소 a 와 b 를 결합하여 다른 요소를 형성. a·b 라고 기. 해당 연산은 결합률과 봉쇄성을 만족할 필요. 집합里에 幺元이 있으며, 각 요소에 역원이 있음

P.S. 역원이란, 각 G 중의 a 에 대해, G 중의 요소 b 가 존재하여, a·b = b·a = e 에 부합. 여기의 e 는 단위원

간단히 말하면:

• 반군: 특정 집합 및 해당 집합 위에서 정의된 이항 연산. 해당 연산은 봉쇄성 (이항 연산 결과는 여전히 집합里) 과 결합률 (좌결합 결과는 우결합 결과와 같음) 을 만족

• 모노이드: 幺元을 포함하는 반군

• 군: 각 요소에 대응하는 역원을 갖는 모노이드

일반에서 특수로. 모노이드는 반군과 군의 사이에 위치. 군이 가장 특수 (조금 직감에 부합하지 않음). 거꾸로 보면, 반군은 모노이드의 범화 (반군은 幺元을 요구하지 않음). 또한 군의 범화 (반군은 각 요소에 역원이 있는 것을 요구하지 않음):

A semigroup generalizes a monoid in that there might not exist an identity element. It also (originally) generalized a group (a monoid with all inverses) to a type where every element did not have to have an inverse, thus the name semigroup.

구문 각도에서 보면, 삼자 관계는 다음과 같습니다:

class Semigroup a where
  -- 결합률을 만족하는 연산 (동시에 봉쇄성도 만족)
  (<>) :: a -> a -> a

class Semigroup a => Monoid a where
  -- 幺元
  mempty  :: a
  -- 결합률을 만족하는 연산 (동시에 봉쇄성도 만족)
  mappend :: a -> a -> a
  mappend = (<>)

class Monoid m => Group m where
  -- 역원을 구하는 연산
  invert :: m -> m

Semigroup(반군) 은 인터페이스 (typeclass). 특정 집합 및 해당 집합 위에서 정의된 일종의 연산을 기술. 해당 연산은 결합률을 만족. 모든 Semigroup 인스턴스는 이 종류의 행동 특징을 가짐

Monoid(모노이드) 도 인터페이스. 특정 집합 및 해당 집합 위에서 정의된 결합률을 만족하는 일종의 연산을 기술. 幺元도 집합里에 있음

Group(군) 도 마찬가지로 인터페이스. 특정 결합을 기술. 해당 집합 위에서 정의된 결합률을 만족하는 일종의 연산. 幺元이 있을 뿐만 아니라, 각 요소에 역원도 있음

P.S. 另外, 모노이드와 범주론에는 일정의 관련이 있음. 和範疇論의 관계 참조

참고 자료

• semigroups: Anything that associates