수반에서 모나드로

2013년 8월 29일 · 태그: haskell, category theory · 원문 · 한국어 번역(원문에서 변경됨)

Haskell에서 제가 가장 좋아하는 구성 중 하나, 즉 수반 함자가 모나드를 만들어 낸다는 사실을 공유하고자 합니다. 범주론에서는 자명한 결과이지만, 이것이 Haskell에서 드러나는 방식은 꽤 아름답습니다.

Haskell에서 Functor(함자)는 Hask의 부분 범주에 있는 대상과 사상(즉, 함수)을 다른 범주의 대상과 사상으로 사상합니다.

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

그리고 함자 법칙을 만족합니다:

fmap id = id
fmap (a . b) = (fmap a) . (fmap b)

가환 도표에서는 대상을 점으로, 사상을 화살표로 그립니다. 문자열 도표에서는 이를 뒤집어 사상을 점으로, 대상을 선으로 그립니다.

함자 합성은 $F:\mathcal{A}\to \mathcal{B}$, $G:\mathcal{B}\to \mathcal{C}$에 대해 $G\circ F:\mathcal{A}\to \mathcal{C}$로 정의되며, 평행한 선으로 그립니다.

newtype FComp f g a = C { unC :: f (g a) }

instance (Functor f, Functor g) => Functor (FComp f g) where
  fmap f (C x) = C (fmap (fmap f) x)

일반적으로 함자의 합성 $F\circ G$는 간단히 $FG$로 씁니다. 도표상으로 합성은 문자열 도표에서 인접한 선분들을 하나로 합칠 수 있게 해 줍니다.

항등 함자( $\text{Id}$ )는 각 사상과 대상을 자기 자신으로 대응시키는 함자입니다.

newtype Id a = Identity { unId :: a }

instance Functor Id where
    fmap f x = Identity (f (unId x))

항등 함자와의 합성은 항등 관계를 이룹니다:

$$F\circ {\text{Id}}_B=F{\text{Id}}_A\circ F=F$$

이는 다음 식들로 확인할 수 있습니다:

left :: Functor f => FComp f Id a -> f a
left (C a) = fmap unId a

right :: Functor f => f a -> FComp f Id a
right a = C $ fmap Identity a

항등 함자를 생략하는 관례를 따르며, 이후의 문자열 도표에서는 이를 점선으로 나타냅니다.

여기서 다루는 맥락에서 자연 변환은 두 Haskell 함자 인스턴스 f와 g에 연관된, 타입 시그니처 (Functor f, Functor g) => forall a. f a -> g a를 갖는 다형 함수입니다. 이는 다음과 같은 타입 동의어로 쓸 수 있습니다.

type Nat f g = forall a. f a -> g a

함자 $F$를 자기 자신으로 대응시키는 항등 자연 변환은 $1_F$로 쓰며, Haskell에서는 그저 (id)입니다. 자연 변환의 합성은 아래에 나타낸 결합 법칙을 따릅니다:

마지막 교환 법칙은 자연 변환을 함자들을 따라 수평으로 추적하든, 함자들 사이의 자연 변환을 수직으로 합성하든 같은 결과에 도달한다는 것을 말합니다.

$$(\alpha \beta )\circ ({\alpha }^{\prime }{\beta }^{\prime })=(\alpha {\alpha }^{\prime })\circ (\beta {\beta }^{\prime })$$

type NatComp f f' g g' = forall a. f' (f a) -> g' (g a)

vert :: (Functor f, Functor f', Functor g, Functor g') =>
         Nat f' g' -> Nat f g -> NatComp f f' g g'
vert a b x = a (fmap b x)

horiz :: (Functor f, Functor f', Functor g, Functor g') =>
          Nat f' g' -> Nat f g -> NatComp f f' g g'
horiz a b x = fmap b (a x)

교환 법칙에 따라 horiz와 vert는 합성에서 서로 교환 가능해야 합니다. Haskell에서 자연 변환 a, b, a', b'에 대해 다음 등식이 성립합니다:

(a . b) `vert` (a' . b') == (a `horiz` a') . (b `horiz` b')

항등 함자와 합성 함자 $FG$ 사이의 자연 변환 $\eta :1_{\mathcal{C}}\to FG$에 대한 도표 예시는 다음과 같이 그립니다:

동형 $F\cong G$는 $FG={\text{Id}}_C$이고 $GF={\text{Id}}_D$라는 의미에서 함자의 합성이 가역임을 뜻합니다. 함자 쌍 $F:D\to C$와 $G:C\to D$ 사이의 수반 $F⊣G$는 이보다 약한 명제로, 다음을 갖는 연관된 자연 변환 쌍 $(F,G,ϵ,\eta )$가 존재한다는 것입니다:

$$ϵ:FG\to 1_{\mathcal{C}}\eta :1_{\mathcal{D}}\to FG$$

이때 다음 삼각 항등식이 성립합니다:

$$(ϵF)\circ (F\eta )=1_F(Gϵ)\circ (\eta G)=1_G$$

이를 그림으로 나타내면 다음과 같습니다:

범주 $C,D$의 관점에서 보면 수반은 어떤 의미에서 “반쪽 동형사상” 또는 “거의 역“이지만, 한쪽 방향에서는 일부 구조가 소실됩니다.

$\eta$와 $ϵ$은 각각 *단위(unit)*와 *쌍대단위(counit)*라고도 부릅니다.

Haskell에는 다음과 같은 타입 클래스가 있는데, 안타깝게도 타입 추론기가 어떤 fmap을 사용할지 추론하려면 함수 종속성(functional dependency)이 필요합니다:

class (Functor f, Functor g) => Adjoint f g | f -> g, g -> f where
  eta     :: a -> g (f a)
  epsilon :: f (g a) -> a

또한 두 개의 다른 자연 변환($\varphi ,\psi$)이 있으며, 이들은 수반 함자 쌍과 함께 수반을 이룹니다. 수반은 수반 쌍을 통해 정의할 수 있으며, Haskell에서는 이것이 가장 편리한 정의입니다

$$\psi ϵ=1_F\varphi \eta =1_G$$

phi :: Adjoint f g => (f a -> b) -> a -> g b
phi f = fmap f . eta

psi :: Adjoint f g => (a -> g b) -> f a -> b
psi f = epsilon . fmap f

특히 $\varphi$와 $\psi$는 함수 집합 (a -> g b)와 (f a -> b) 사이의 동형사상을 이루며, 이는 위의 삼각 항등식과 같은 관계입니다. 또는 $\eta$와 $ϵ$을 $\varphi$와 $\psi$를 통해 표현할 수도 있습니다.

phi eta = id
psi epsilon = id

Haskell 프렐류드에는 정준적인 수반, 즉 curry와 uncurry가 있습니다:

$$\text{curry}⊣\text{uncurry}$$

instance Functor ((,) a) where
  fmap f (x,y) = (x, f y)

instance Functor ((->) a) where
  fmap f g = \x -> f (g x)

이 두 함자 인스턴스로부터 Adjoint 인스턴스를 구성할 수 있습니다:

instance Adjoint ((,) a) ((->) a) where
  eta x y = (y, x)
  epsilon (y, f) = f y

$(ϵF)\circ (F\eta )$와 $(Gϵ)\circ (\eta G)$가 모두 항등 자연 변환( id )으로 환원됨을 보임으로써 이 정의에 대해 삼각 등식이 성립함을 확인할 수 있습니다.

a0 :: (a -> (b -> c)) -> a -> (b -> c)
a0 f = \f -> fmap (epsilon . fmap f) . eta
a0 f = fmap (\(y, f) -> g f y) . eta
a0 f = \x y -> f x y

a1 :: ((a, b) -> c) -> (a,b) -> c
a1 f = epsilon . fmap (fmap f . eta)
a1 f = epsilon . fmap (\x y -> f (y, x))
a1 f = \(x, y) -> f (x, y)

모나드는 두 개의 자연 변환을 갖는 자기 함자 $T:C\to C$로서 $(T,\mu ,\eta )$이며, 다음과 같은 일반적인 법칙을 따른다는 것을 우리는 알고 있습니다:

$$\mu \circ T\mu =\mu \circ \mu T\mu \circ T\eta =\mu \circ \eta T=1_T$$

기하학적 직관으로 보면, 모나드 법칙은 스트링 다이어그램의 위상적 성질로 반영됩니다. $\mu$와 $\eta$는 모두 반사 대칭을 보이며, $\eta$를 위상적으로 곧게 펴면 항등 함자를 얻습니다.

Haskell에서는 모나드 타입 클래스를 자기 함자와 ($\mu ,\eta$), 또는 join과 return으로부터 일반적으로 구성할 수 있습니다.

class (Functor t) => Monad t where
  eta :: a -> (t a)
  mu  :: (t (t a)) -> (t a)

  (>>=) :: t a -> (a -> t b) -> t b
  ma >>= f = mu . fmap f

return = eta
join = mu

그러나 곧바로 드러나지 않는 사실은, 모든 수반 함자 쌍이 범주 $C$ 위의 모나드 $(T,\mu ,\eta )$를 낳는다는 점입니다. 이 모나드는 함자들의 합성으로 유도되어, 바탕이 되는 수반의 단위와 쌍대단위를 통해 자기 함자와 자연 변환들을 만들어 냅니다:

$$\begin{array}{rlrlrlr}T& =G\circ F& :& C\to C\mu & =Gϵ& :& T^2\to T\end{array}$$

class Adjoint f g => Monad f g where
  muM :: g (f (g (f a))) -> g (f a)
  muM = fmap epsilon

  etaM :: a -> g (f a)
  etaM = eta

  (>>=) :: g (f a) -> (a -> g (f b)) -> g (f b)
  x >>= f = muM (fmap (fmap f) x)

이에 대한 기하학적 직관은 명확합니다:

그런 다음 모나드로부터 일반적인 방식으로 클라이슬리 범주를 구성할 수 있습니다.

class (Adjoint f g, Category c) => Kleisli c f g where
  idK :: c x (g (f x))
  (<=<) :: c y (g (f z)) -> c x (g (f y)) -> c x (g (f z))

instance Monad f g => Kleisli (->) f g where
  idK = eta
  g <=< f = muM . fmap (fmap g) . f

instance Kleisli c f g => Monoid (c a (g (f a))) where
  mempty  = idK
  mappend = (<=<)

돌이켜 보면 이는 자명하지만, 중요하게도 더 중요한 질문으로 우리를 이끕니다: 모나드로부터 수반을 복원할 수 있는가? 답은 ’그렇다’입니다…