모나드(monad)는 그냥 자기 함자(endofunctor) 범주의 모노이드(monoid)일 뿐인데, 대체 뭐가 어렵다는 거냐?
-1990, 필립 와들러 (하스켈 설계 책임자)-

하스켈은 대수적인 자료형을 조작하는 범주론(Category theory)에 따라 프로그래밍 언어를 설계했습니다. 우리는 범주론의 약간의 개념과 이를 구현한 하스켈에 구현체에 대해 알아보겠습니다.

Category Theory(범주론)

범주론(Category Theory)은 수학의 한 분야로, 대수 구조, 대상, 사상 등을 추상적인 개념으로 다룹니다.

먼저 3가지 수학적 개념을 이해하면 하스켈이 어떤 개념을 바탕으로 설계되었는지 이해하기 쉽습니다.

• 대상(object)

• 사상(morphism)

• 대수 구조(algebraic structure)

Object(대상)

대상은 범주론에서 가장 기본적인 개념으로, 범주(Category) 내에서 객체를 나타내는 추상적인 요소입니다. 간단히 말해서, 대상은 어떤 것의 이름이며, 어떤 집합을 가리키거나 특정한 구조를 갖는 객체를 표현합니다.

Morphism(사상)

사상은 대상과 대상 사이의 변환을 나타내는 개념입니다. 범주론에서 사상은 대상들 간의 관계를 추상화하여 표현합니다. 다른 말로 화살표(arrow)라고도 합니다. 사상은 한 대상을 다른 대상으로 대응시키는 규칙 또는 함수를 나타내며, 대상들 간의 구조를 보존하는 변환을 의미합니다.

Algebraic Structur(대수 구조)

대수 구조는 어떤 집합에 대한 연산들을 추상화하는 수학적인 구조를 의미합니다. 대수 구조는 집합과 그 집합 위에서 정의된 연산들로 구성되며, 이 연산들은 일정한 성질을 만족합니다. 대수 구조에는 다양한 종류가 있으며, 대표적으로 그룹(Group), 반군(Semigroup), 환(Ring) 등이 있습니다.

In Haskell

GHC Compiler Code

GHC 컴파일러의 소스 코드 ghc/libraries/base/GHC/Base.hs를 보면 type class 선언을 찾을 수 있습니다.

-- ** Semigroups and Monoids
Semigroup((<>)),
Monoid(mempty, mappend, mconcat),

-- ** Functors and Monads
Functor(fmap, (<$)), (<$>),
Applicative(pure, (<*>), (*>), (<*)),
Monad(((>>=), (>>), return),
MonadFail(fail),
mapM_, sequence_, (=<<),

Algebraic Structur(대수 구조)

• 집합(Set): 아무런 연산이 정의되어 있지 않는 대수 구조입니다.

• 마그마(Magma) :이항 연산(bBinary operation)을 갖춘 집합(Set)입니다.

• 반군(Semigroup):결합 법칙(associative)을 만족시키는 마그마(Magma)입니다.

• 모노이드(Monoid): 항등원 (identity)을 갖는 반군(Semigroup)입니다.

• 군(Group): 모든 원소가 가역원(inverse)인 모노이드(Monoid)입니다.

Haskell에는 두 값을 결합하는 이항 연산(binary operation)을 정의하는 대수적인 자료형을 조작하는 추상화 개념으로 Semigroup과 Monoid가 있습니다.

Semigroup(반군)

Semigroup은 단일 연산(결합 연산)을 정의하는 대수적 구조입니다. 두 값을 가져와서 하나의 결과를 만들어내는 연산이며, 이 연산은 결합 법칙(Associativity)을 만족해야 합니다. 즉, 어떤 순서로 연산을 수행하더라도 결과가 같아야 합니다.

Semigroup은 중요한 속성 한 가지를 가지고 있습니다:

1. 결합 법칙(Associativity): Semigroup의 연산은 결합 법칙을 만족해야 합니다.

Haskell에서 Semigroup는 Data.Semigroup 모듈에 정의되어 있으며, <> 연산자를 통해 결합 연산을 수행합니다. 주로 리스트나 숫자, 문자열 등에서 사용됩니다.

• Associativity(결합법칙) - x <> (y <> z) = (x <> y) <> z

class Semigroup a where
 (<>) :: a -> a -> a

 sconcat :: NonEmpty a -> a
 sconcat (a :| as) = go a as where
  go b (c:cs) = b <> go c cs
  go b []   = b

 stimes :: Integral b => b -> a -> a
 stimes = stimesDefault

Monoid(모노이드)

Monoid는 Semigroup의 확장 개념으로, 항등원(identity)을 가지는 대수적 구조입니다. 항등원은 어떤 연산을 수행해도 값에 변화가 없는 특별한 원소를 의미합니다.

Monoid는 두 가지 중요한 속성을 가지고 있습니다:

1. 결합 법칙(Associativity): Monoid의 연산은 결합 법칙을 만족해야 합니다.

2. 항등원(identity): Monoid는 특정 항등원을 가져야 합니다. 이 항등원은 Monoid의 연산에 대해 항상 결과를 변화시키지 않습니다.

Haskell에서 Monoid는 Data.Monoid 모듈에 정의되어 있습니다. mempty 함수를 통해 항등원을 얻을 수 있으며, mappend (또는 <>) 함수를 통해 결합 연산을 수행합니다.

• Left identity(좌항등원) - mempty <> x = x

• Right identity(우항등원) - x <> mempty = x

• Associativity(결합법칙) - x <> (y <> z) = (x <> y) <> z

• Concatenation(접합) - mconcat = foldr (<>) mempty

class Semigroup a => Monoid a where
 mempty :: a

 mappend :: a -> a -> a
 mappend = (<>)

 mconcat :: [a] -> a
 mconcat = foldr mappend mempty

Morphism(사상) of Category Theory

수학적 구조를 보존하는 추상화한 함수(function)에 해당하는 개념입니다. 특히 준동형 사상(homomorphism)은 두 대수적 구조(structure) 사이의 모든 연산과 관계를 보존하는 사상, 또는 동일한 종류의 대수적 구조 사이에 정의된 대수적 구조를 보존하는 함수입니다.

• 단사(Injective)인 준동형 사상은 단사 사상(Monomorphism)이라고 부릅니다.

• 전사(Surjective)인 준동형 사상은 전사 사상(Epimorphism)이라고 부릅니다.

• 단사 사상이자 전사 사상인 준동형 사상을 동형 사상(Isomorphism)이라고 부릅니다. 두 대상(object) 사이에 동형 사상(isomorphism)이 존재하는 경우 서로 동형(同型, 영어: isomorphic)이라고 합니다.

• 정의역(domain)과 공역(codomain)이 같은 준동형 사상은 자기 사상(Endomorphism)이라고 부릅니다.

• 자기 사상이면서 동형 사상인 준동형 사상을 자기 동형 사상(Automorphism)이라고 부릅니다.

• 벡터 공간 사이에 정의된 준동형 사상은 선형 변환(Linear Transformation), 선형 사상(Linear Map) 등으로 불립니다.

Functor(함자)

Functor는 두 대수 구조(algebraic structur) 사이에 함수(function)에 해당하는 대수 구조에 해당합니다.

Haskell에서 Functor는 값을 담고 있는 컨테이너 타입(예: 리스트, Maybe 등)을 매핑(mapping)하는 데에 사용되는 타입 클래스입니다. 컨테이너 안의 값들에 함수를 적용하여 새로운 값을 얻을 수 있습니다.

Haskell에서 Functor는 Data.Functor 모듈에 정의되어 있으며, fmap 함수를 통해 값을 변환할 수 있습니다. Functor의 대표적인 예시로는 리스트와 Maybe가 있습니다.

• 대상(object)을 대상(object)으로 대응(map)

• 사상(morphism)을 사상(morphism)으로 대응(map)

• Identity(항등원) - fmap id == id

• Composition(함수합성) - fmap (f . g) == fmap f . fmap g

class Functor f where
    fmap :: (a -> b) -> f a -> f b

 (<$) :: a -> f b -> f a
 (<$) = fmap . const

Applicative(적용자)

Applicative는 Functor를 보완하여, 컨테이너 안의 함수를 컨테이너 안의 값에 적용하는 개념입니다. 즉, 컨테이너 안에 담겨있는 함수와 값을 모두 컨테이너 안에 넣어서 적용하는 것을 의미합니다.

Haskell에서 Applicative는 Control.Applicative 모듈에 정의되어 있습니다. <*> 연산자를 사용하여 함수와 값을 적용합니다.

• Identity(항등원) - pure id <*> v = v

• Composition(함수합성) - pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

• Homomorphism(준동형사상) - pure f <*> pure x = pure (f x)

• Interchange(교환법칙) - u <*> pure y = pure ($ y) <*> u

class Functor f => Applicative f where
 pure :: a -> f a

 (<*>) :: f (a -> b) -> f a -> f b
 (<*>) = liftA2 id

 liftA2 :: (a -> b -> c) -> f a -> f b -> f c
 liftA2 f x = (<*>) (fmap f x)

 (*>) :: f a -> f b -> f b
 a1 *> a2 = (id <$ a1) <*> a2

 (<*) :: f a -> f b -> f a
 (<*) = liftA2 const

Monad(모나드)

Monad는 Applicative를 보완하여, 컨테이너 안의 값을 추출한 후에 함수를 적용할 수 있도록 하는 개념입니다. 이를 통해 값을 다른 컨테이너에 넣어주거나, 계산 순서를 제어할 수 있습니다.

Haskell에서 Monad는 Control.Monad 모듈에 정의되어 있습니다. >>= 연산자를 사용하여 값을 추출하고 함수를 적용합니다.

• Left identity(좌항등원) - return a >>= k = k a

• Right identity(우항등원) - m >>= return = m

• Associativity(결합법칙) - m >>= (\x -> k x >>= h) = (m >>= k) >>= h

class Applicative m => Monad m where
 return :: a -> m a
 return = pure

 (>>=) :: forall a b. m a -> (a -> m b) -> m b

 (>>)  :: forall a b. m a -> m b -> m b
 m >> k = m >>= \_ -> k

마무리

Semigroup와 Monoid는 모두 대수적인 연산을 정의하는데 사용되는 타입 클래스이지만, Monoid는 Semigroup의 확장 개념으로서 항등원을 가지는 특징을 갖습니다. 이들을 적절하게 사용하여 여러 자료형을 조작하고 추상화할 수 있습니다.

Functor, Applicative, Monad는 모두 자료형을 조작하고 추상화하는 방법들로서, Functor는 값을 변환하는 데에 초점을 두고, Applicative는 함수와 값을 모두 컨테이너에 담아서 적용하는 데에 초점을 두며, Monad는 Applicative를 보완하여 값을 추출하고 함수를 적용하는 데에 초점을 둡니다. 이들을 적절하게 조합하면 매우 강력한 추상화와 제어 구조를 구현할 수 있습니다.