Monad 2 - Type classes
Before starting
1편을 통해 모나드가 뭐고 이게 왜 필요한지 알게 되었다. 모나드를 간단하게 복습하면 아래의 2가지 함수를 가진 Applicative Functor이다.
1
2
3
class Applicative m => Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
그런데 이 설명은 불완전하다. 아직 Applicative Functor가 뭔지에 대해선 이야기 하지 않았기도 하고, 정말로 이걸로 충분한지에 대한 검증이 필요하다. 이번 글에서는 이 부족한 부분들에 대해서 이야기하고, 추가로 모나드와 엮이는 타입들을 몇 가지 살펴보자.
Functor
모나드에 대한 것은 잠깐 잊고, Option, List 등의 컨텍스트에 대해 생각해보자. 이들은 데이터 앞에 붙어서 추가적인 정보를 제공해준다. 그럼 이러한 컨텍스트를 유지하면서 내부 값들을 조작하기 위해 가져야 할 기능은 뭐가 있을까? 가장 먼저 생각나는 것은 외부의 연산자를 이용할 수 있게 해주는 기능이다. 이것조차 없으면 내부 값들을 가지고 계산하기 위해선 컨텍스트에서 꺼내야만 한다. 반드시 컨텍스트에서 꺼내야 계산을 할 수가 있다면 그 컨텍스트를 유지할 이유가 있겠는가?
이 기능을 함수로 쓴다면 다음과 같은 타입을 가질 것이다.
1
map :: (a -> b) -> f a -> f b
즉, a -> b라는 컨텍스트 외부 함수와 이 컨텍스트가 적용된 값 f a가 있으면 그를 통해 f b를 계산하게 해준다.
이러한 함수를 가진 타입을 Functor라고 부른다. 보다 구체적으로, 하스켈에서 Functor는 다음과 같이 정의되어 있다.
1
2
class Functor f where
fmap :: (a -> b) -> f a -> f b
여기서 fmap 함수는 <!> 연산자로도 표기한다.
만일 어떤 컨텍스트가 Functor조차 아니라면, 이 컨텍스트 내부의 값은 반드시 계산을 완료해서 primitive value로 치환해야만 우리가 마음대로 조작을 할 수 있게 된다. 그 이야기는 즉 컨텍스트를 유지한 상태로는 그 어떠한 조작도 불가능하다는 이야기와 동일하고, 이런 상황 속에선 모나드고 뭐고 제대로 정의가 될 수가 없다. 그렇기 때문에 모나드가 Functor 위에서 정의되어야만 한다는 것을 쉽게 알 수 있다.
여담으로, fmap이라는 이름에서 알 수 있듯이, 굳이 함수형 언어가 아니더라도 요새 많은 언어들이 제공해주는 map 함수가 이와 동일함을 알 수 있다. 예를 들자면 C#의 Select나 JS의 map 등이 이 fmap과 정확히 동일한 기능을 제공한다.
Applicative Functor
위의 고찰을 통해 Functor라는 것은 컨텍스트의 가장 기본적인 타입임을 알 수 있었다. 그런데 fmap만 있는 컨텍스트는 일단 컨텍스트라고 부를 수는 있지만 동일한 컨텍스트끼리의 연산을 하려면 외부 연산에 의존해야만 한다. 그래서 특정 컨텍스트에 특화된 연산을 정의하기 위해 컨텍스트 내부에 함수를 정의하면 정작 사용할 수 없는 이상한 상황에 처하게 된다.
이러한 현상을 방지하기 위해선 아래의 함수가 필요하다.
1
a :: f (a -> b) -> f a -> f b
위의 제시된 상황 그대로, 컨텍스트 내부에 정의된 함수 f (a -> b)가 있으면 이를 f a에 그대로 적용시킬 수 있는 함수이다.
이러한 함수를 가진 Functor를 Applicative Functor, 혹은 줄여서 Applicative라고 부른다. 하스켈에서는 다음과 같이 정의되어 있다.
1
2
3
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
여기서 <*> 연산자는 “Apply”라고 부른다.
만일 어떤 Functor가 Applicative는 아니라면, 이 Functor는 내부에 값을 저장하고 이를 조작할 수는 있으나 내부에 함수를 만들 수 없다는 이야기가 된다. 함수형 언어에서 함수를 마음대로 정의하지 못한다는 것은, 이 Functor가 독립적인 기능을 하기는 좀 어렵다는 것을 의미한다.
그럼 마지막으로 Applicative와 모나드의 관계를 생각해보자. 우선 Applicative의 pure와 모나드의 return은 이름만 다를 뿐 함수 자체는 완벽히 동일하고, 이 함수의 필요성에 대해서는 1편에서 언급했으니 생략한다.
그럼 이제 Apply와 Bind를 비교해보면, Apply는 컨텍스트 외부에서 독립적인 연산을 지원하는 연산자고, Bind는 컨텍스트 내부에서 순차 실행을 지원하는 연산자다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Applicative
let result1 =
(fun x y z -> x + y + z)
<!> Some 1
<*> Some 2
<*> Some 3
// Monad
let result2 =
option {
let! x = Some 1
let! y = Some (x + 1)
let! z = Some (x + y)
return x + y + z
}
위의 코드가 Applicative와 모나드의 차이를 잘 보여주고 있다. Apply 연산자는 어디까지나 각각의 독립적인 컨텍스트에 대한 연산만을 제공해준다. 하지만 Bind 연산자는 M a -> (a -> M b) -> M b로 정의되며, 그 중에서도 a -> M b 부분을 보면 알 수 있듯이 이미 컨텍스트가 추가된 M a라는 값을 받으면서 모나드 내부의 연산은 그 컨텍스트가 제거된 a를 인자로 요구하고 있다. 이 말은 모나드 내부에서는 컨텍스트가 제거된 값에 직접 접근하여 연산이 가능하다는 의미이고, 그렇기 때문에 모나드 내에서는 이전 결과에 의존하는 연산, 즉 순차 실행이 가능하다는 의미가 된다.
다만, 모나드의 본질을 생각해보면, Apply가 없는 모나드는 어딘가 부족하다. 모나드라는 것이 근본적으로 side-effect를 자유롭게, 함수형 언어의 방식으로 다루기 위해 고안된 개념인 만큼, 모나드 내부에서의 자유로운 연산만으로는 이 목적을 달성하기 어렵고, Apply를 같이 지원하여 동일한 모나드끼리의 연산 역시 지원해야 자연스럽다. 그렇기 때문에 모나드는 Applicative 위에서 정의되어야 하며, 반대로 Applicative는 모나드보다 약한 개념으로 취급된다.
Monad Law
그럼 정말 Applicative이면서 Bind와 Return이 타입에 맞게 제공되기만 하면 전부 모나드일까? 다음의 예시를 보자.
1
2
3
4
5
6
7
8
9
10
type WeirdOption<'a> =
| WeirdSome of 'a
| WeirdNone
let weirdBind m f =
match m with
| WeirdSome x -> WeirdNone
| WeirdNone -> WeirdNone
let weirdReturn x = WeirdSome x
이러한 타입 WeirdOption은 모나드일까?
1
2
3
weirdReturn 5 |> weirdBind (fun x -> weirdReturn (x * 2))
// Expected: WeirdSome 10
// Actual: WeirdNone
위의 코드를 보면 우리가 기대한 값과 실제로 나오는 값이 전혀 다름을 알 수 있다. 이 때문에 모나드에 대한 추가적인 규칙들이 필요하고, 우리는 이걸 “Monad Law”라고 부른다. 이 법칙에는 아래의 3가지가 있다.
- Left Identity -
x >>= f ≡ f x
return 한 후 바로 bind를 하면 그냥 함수를 호출한 것과 동일해야만 한다. 만일 Left Identity를 만족하지 못하게 되면, 모나드를 거쳐서 함수를 적용하는 것이 그 함수를 그냥 적용하는 것과 같다는 것을 보장할 수 없게 된다.
- Right Identity -
m >>= return ≡ m
bind 한 후 바로 return을 하면 원래 값이 그대로 나와야만 한다. 만일 Right Identity를 만족하지 못하게 되면, return이 정말 모나드를 붙이기만 하는 함수인지를 보장할 수 없게 된다.
- Associativity -
(m >>= f) >>= g ≡ m >>= (fun x -> f x >>= g)
bind 연산자에 대한 결합법칙이 성립해야 한다. 만일 결합법칙을 만족하지 못하게 되면 모나드 내에서 (일반적으로 순서에 상관없어 보이는 연산일지라도) 순서가 달라지면 결과가 달라지는 상황이 나오게 될 수 있다.
Alternative와 MonadPlus
위의 내용들을 통해 비로소 모나드를 제대로 정의할 수 있게 되었다. 이제부터는 기본적인 모나드만으론 해결할 수 없는 상황들을 살펴보자.
때때로 계산을 하면서, 그 계산이 실패할 가능성이 존재하는 경우가 있다. 계산 자체나 인자로 넘어온 값에서의 문제도 있을 수 있고, REST API 호출 실패나 파일 등을 포함한 OS 레벨의 이슈, 혹은 기타 다양한 이슈가 발생할 수 있다. 이러한 상황들은 함수형 언어에서는 어떻게 처리해야 할까?
이 문제를 해결할 방법은 다양하게 있겠지만, 결국 순수성을 잃지 않고 함수형 스타일로 풀어내려면 패턴 매칭을 시도하는 것이 가장 나을 것으로 보인다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let parseAsInt (s: string) =
match System.Int32.TryParse(s) with
| true, v -> Some v
| _ -> None
let parseAsFloat (s: string) =
match System.Double.TryParse(s) with
| true, v -> Some (int v)
| _ -> None
let parseNumber s =
match parseAsInt s with
| Some v -> Some v
| None -> parseAsFloat s
parseNumber "3.14" // Some 3
이렇게 구현해두면 그럭저럭 실패 상황에 대응할 수 있게 된다. 그런데 솔직히 너무 번거롭다. 컨텍스트 레벨에서 해당 기능을 지원해주면 좀 더 편할 것 같다는 생각이 들지 않는가?
그래서 컨텍스트에 관련 함수를 추가하여, 실패 상황을 직접 지원해보려고 한다. 위의 코드를 통해 어떤 것이 필요할지 생각해보면, 우선 “실패 상황”을 뜻하는 값 1개가 필요하다. 그리고 연산이 실패하면 대신 그 “실패 상황”을 의미하는 값을 리턴해주는 함수도 필요하다.
1
2
fail :: f a
or :: f a -> f a -> f a
즉, 컨텍스트 f에 대해서 위의 두 함수가 필요하다는 것을 알 수 있다. 물론 컨텍스트에 속한다는 것을 명확히 하기 위해 fail의 값이 f a로 표현된거지, 실제로는 실패임을 뜻하는 다른 형태로 제공될 것이다.
이러한 타입을 Alternative라고 부른다. 하스켈에서 Alternative는 다음과 같이 정의된다.
1
2
3
class Applicative f => Alternative f where
empty :: f a
(<|>) :: f a -> f a -> f a
여기서 <|> 연산자는 “Or”라고 부른다.
물론 Alternative에도 위의 Monad Law와 같이 만족해야만 하는 법칙들이 몇 가지 있다.
- Left Identity -
empty <|> m ≡ m - Right Identity -
m <|> empty ≡ m - Associativity -
(m1 <|> m2) <|> m3 ≡ m1 <|> (m2 <|> m3)
즉, Alternative는 항등원이 존재하고 결합법칙을 만족해야 한다. 이를 조금 더 짧게 쓰면 “Alternative는 모노이드다”라고 말할 수 있다.
한 가지 주목해야 할 점은, Alternative는 Applicative 위에서 정의된다는 점이다. 조금만 생각해보면, 기본적인 계산이 되어야 실패 상황을 다룰 필요성이 생기며, 그렇기 때문에 Alternative라는 타입은 이 컨텍스트가 Applicative일 때부터 의미가 생긴다는 것을 알 수 있다.
물론 그렇다고 해서 모나드가 Alternative의 기능을 가질 수 없다는 소리는 아니다. 모나드이면서 Alternative인 타입을 MonadPlus라고 부르며, 하스켈에서는 다음과 같이 정의된다.
1
2
3
class Monad m => MonadPlus m where
mzero :: m a
mplus :: m a -> m a -> m a
함수 및 연산자의 이름이 empty와 <|>에서 mzero와 mplus로 바뀐 것만 빼면 동일하다. 함수 이름이 mzero와 mplus로 바뀐 이유는 역시 이들이 모노이드를 형성하기 때문이다.
그리고 Monad는 기본적으로 Bind 연산자가 있는 만큼, 이와 관련된 추가적인 법칙이 더 존재한다.
- Left Zero -
mzero >>= f ≡ mzero - Right Zero -
m >>= (fun _ -> mzero) ≡ mzero
사실 위의 법칙 때문에 “Alternative이면서 Monad인 타입”이라고 부르지 않고 MonadPlus라고 부르는 것이기도 하다. 서로 다른 두 개념이 만나서 새로운 법칙이 생겼으니까.
여담으로 Right Zero 법칙은 너무 강하다는 의견도 있을 정도로 필수적인 것은 아니다. Right Zero 법칙은 m을 항상 mzero로 돌릴 수 있다는 이야기와 동일하고, 이는 MonadPlus에서 다루고자 하는 상황의 범위를 넘어선 이야기이기 때문이다.
Foldable
이번엔 다음과 같은 상황을 생각해보자. 여러 데이터를 한 컨텍스트에 저장했다. 그리고 이 데이터를 왼쪽에서부터 하나씩 합친 결과물을 얻고 싶다. 물론 합치는 방법은 자유다.
이러한 상황은 생각보다 자주 나온다. 여러 개의 데이터를 저장할 수 있는 collection에서 이들의 합이나 평균, 카운트, 최댓값, 최솟값 등 기초적인 통계 함수를 제공하는 것은 이제 비단 함수형 언어 뿐만이 아니라 많은 언어에서 지원하고 있으며, 전부 위의 상황에 대응된다.
이러한 기능의 일반화를 하스켈을 비롯한 함수형 언어에서는 “접는다”, 즉 fold라고 표현한다. 마치 리스트를 왼쪽에서부터 차례대로 접어, 한 개의 값만 남긴다는 의미이다.
그럼 이 fold의 타입은 어떻게 될까?
1
(((z `f` a) `f` b) `f` c) -- fold f z [a, b, c]
fold의 타입을 바로 생각하긴 좀 복잡하니 간단한 예시를 들어 fold가 수행할 작업을 생각해보면 위의 코드와 같을 것이다. 즉, fold는 함수 f와 초기값 z, 그리고 값이 여러 개 들어있는 컨텍스트를 인자로 받는다. 그리고 컨텍스트 내부의 각각의 원소들에 대해 이전 결과와 다음 원소를 인자로 삼아 f를 반복적으로 적용해야 한다. 이 때 첫 번째 원소에 대해 적용할 때에는 “이전 결과”라는 것이 존재하지 않으니 초기값을 인자에 넣어야 한다. 그렇게 반복적으로 f를 적용한 후 나온 값 1개를 리턴하면 fold의 모든 작업이 완료된다.
이제 위의 동작에 맞게 fold 함수를 정의해보자. 먼저 값이 들어있는 컨텍스트의 타입을 c a, 초기값의 타입을 b라고 하자. 이러면 반복적으로 적용해야 할 함수 f는 컨텍스트 내부의 타입 a와 초기값의 타입 b를 인자로 받아 b를 리턴해야 한다. 즉 a -> b -> b가 될 것이다.
1
fold :: (a -> b -> b) -> b -> c a -> b
즉 fold 함수는 위와 같은 타입이 될 것이다.
이러한 타입을 Foldable이라고 부른다. 하스켈에서 Foldable은 다음과 같이 정의된다.
1
2
3
class Foldable f where
foldr :: (a -> b -> b) -> b -> f a -> b
foldMap :: Monoid m => (a -> m) -> f a -> m
이 정의를 보면 의문점이 몇 가지 생긴다.
첫째로, foldr 함수는 위의 고찰에서 얻은 함수와 동일한데, 그럼 foldMap은 뭘까? 앞에서 fold 함수는 접을 때 필요한 함수 f와 초기값 z가 필요하다고 했었다. 그런데 초기값, 즉 항등원과 결합성 연산이 같이 제공되면 모노이드가 떠오른다. 그래서 foldr에서 초기값과 함수를 따로따로 제공받던 것을, 그에 해당하는 모노이드 타입 m 하나만 받는 것으로 대체할 수 있다. 반대로 생각해도 마찬가지다. 모노이드 m을 제공하여 foldMap을 수행할 수 있다면, 그 모노이드의 항등원과 연산을 풀어서 써서 따로 제공하면 그게 곧 foldr이 된다. 따라서 실제로는 위의 둘은 사실상 같은 함수라 하나만 구현해도 나머지 하나는 자동으로 구현된 셈이다.
둘째로, Foldable은 그 정의에 다른 기본 요소가 아무것도 필요하지 않다. 심지어 Functor조차도 필요없다. 이는 Foldable은 내부 원소들을 직접 조작하는 것이 아니기 때문이다. 실제로 foldr 함수를 수행하는 데에 있어서, 컨텍스트 내부의 값 자체에 대해서는 어떠한 연산도 하지 않았다. 그렇기에 Foldable은 Functor 계열과는 무관한 타입이다.
물론 foldMap같은게 있으니 Foldable이 Functor이기도 하면 좀 편하긴 하지만, 어쨌건 이론상으론 둘은 무관하기 때문에 Functor가 아닌 Foldable 타입 같은 것도 존재할 수 있다. 물론 모나드이면서 Foldable인 타입도 당연히 존재하고, 오히려 이쪽이 더 일반적이다. 다만 MonadPlus와는 다르게 기존 모나드의 연산인 return과 bind와 결합해서 새로운 성질이나 법칙을 만들어내지는 않기 때문에 이러한 타입을 지칭하는 별도의 이름은 딱히 없다.
Traversable
마지막으로 볼 상황은 순회다. 순회를 함수형 컨셉에 맞게 조금 더 풀어쓰면 컨텍스트 내부의 값들 각각에 대해 내가 원하는 함수를 정의해서 그 결과를 도출하고 싶다는 의미이다.
사실 기존에 우리는 이미 이와 관련된 함수나 타입을 알고 있다. fmap을 제공하는 Functor, 그리고 foldMap을 제공하는 Foldable이다.
1
2
3
4
5
6
7
instance Functor [] where
fmap _ [] = []
fmap f (x:xs) = f x : fmap f xs
instance Foldable [] where
foldMap _ [] = mempty
foldMap f (x:xs) = f x <> foldMap f xs
여기서 <>는 mappend라고 부르며, mempty와 함께 모노이드 타입을 형성한다.
각설하고, 위 코드는 순회가 필요한 타입이라고 하면 대표적으로 떠오르는 리스트에 대한 Functor 및 Foldable의 인스턴스다. 리스트에 fmap f을 쓰면 각 원소에 f를 적용하고 그 결과를 리스트로 재구축하고, foldMap f를 쓰면 각 원소에 f를 적용하고 그 결과를 <>로 결합한다. 이와 같이 fmap과 foldMap을 쓰면 우리가 원하는 순회를 이미 수행하는 것처럼 보인다. 그러나 이 둘로는 모든 상황에 대응할 수 없어서 문제가 된다.
아래와 같은 함수를 생각해보자.
1
2
let validate number =
if number < 0 then None else Some number
이 함수를 리스트에 적용해서, 리스트에 음수가 하나도 없으면 원래 리스트에 Some을 붙여서, 그게 아니라면 None을 반환하게 하고 싶다. 이 상황에서 fmap과 foldMap은 도움이 되지 않는다. fmap을 사용하면 List<int option>이 나오는거지 Option<int list>가 나오는 것이 아니다. foldMap의 경우 리턴 값이 fold하기 위해 고른 모노이드의 구조로 대체되는데, 이걸 Option<int list>로 변환할 방법이 없다. 즉, fmap과 foldMap만 가지고는 우리가 원하는대로, 각 원소를 순회하여 그걸 기반으로 리스트 구조를 재생성하는 방법을 찾을 수 없게 된다.
이러한 작업을 하려면 어떤 함수가 필요할까? 가장 먼저 생각나는 것은 fmap을 통해 얻은 int option의 리스트에서, 이 각각의 int option들을 하나의 option으로 결합하는 함수다. 즉 List<int option> -> Option<int list> 형태의 함수가 필요하다.
그럼 이제 List와 Option 대신 임의의 컨텍스트 t와 f에 대해 일반화를 해보면 어떨까? 순회를 위해 필요한 함수의 형태는 t (f a) -> f (t a)이다. 여기서 f는 그냥 아무 컨텍스트이기만 하면 될까?
f가 해줘야 하는 일은, 흩어진 f a들을 모아 하나의 컨텍스트로 결합해야 하는 것이다. 그리고 이건 Applicative에 있는 Apply 연산자가 하는 일이다. 따라서 이상의 내용을 정리하면 다음과 같다.
1
sequence :: Applicative f => t (f a) -> f (t a)
이러한 타입을 Traversable이라고 부른다. 하스켈에서 Traversable은 다음과 같이 정의된다.
1
2
3
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
sequenceA :: Applicative f => t (f a) -> f (t a)
이 정의에서도 몇 가지 의문점이 남는다.
우선 sequenceA가 위에서 정의해본 sequence 함수와 같다는 것을 알 수 있다. 그러면 traverse 함수는 뭘까? Foldable에서 foldr과 foldMap과의 관계와 비슷하게, Traversable에서 traverse와 sequenceA는 서로를 이용해 정의할 수 있는 관계이다. 구체적으로, 다음과 같이 서로가 서로를 정의할 수 있다.
1
2
traverse f = sequenceA . fmap f
sequenceA = traverse id
당연하지만 정의에서도 적혀 있듯이 Traversable은 Functor 위에서 정의되기 때문에 fmap을 사용할 수 있다.
다음으로 Traversable은 Functor와 Foldable을 모두 필요로 한다. 위의 sequenceA나 traverse는 결국 fmap으로 일단 묶은 타입을 다시 재구성하는 함수이기 때문에, 진정한 순회를 위해서는 fmap이 여전히 필요하다. 그래서 Traversable은 Fuctor 위에서 정의된다. foldMap은 사실 위의 논의에서 직접적으로 필요하지는 않았은데, traverse를 구현하면 foldMap은 자동적으로 같이 딸려오기 때문에 Traversable이 Foldable을 포함하는 개념이 된다.
다음과 같이 traverse를 통해 foldMap을 구현할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
newtype Const a b = Const { getConst :: a }
instance Functor (Const a) where
fmap _ (Const x) = Const x
instance Monoid a => Applicative (Const a) where
pure _ = Const mempty
Const x <*> Const y = Const (x `mappend` y)
...
foldMap f = getConst . traverse (Const . f)
물론 이론상 가능하다는거고 실제론 foldMap을 따로 구현하는 것이 더 낫긴 하다.
여하튼 Traversable은 Functor 위에서 정의되기 때문에 당연히 모나드이면서 Traversable인 타입이 존재할 수 있다. 물론 이 경우에도 이를 지칭하는 별다른 이름은 없는데, Foldable과 같은 이유다. 즉, traverse가 Bind와 결합해서 새로운 성질이나 법칙을 만들어내지는 않는다.
마무리
이렇게 Functor, Applicative, Alternative, Foldable, Traversable에 대해 알아봤다. 여기에 더해 이 시리즈의 본 주제인 모나드까지 포함하면 “계산의 합성”을 다루는 기본적인 타입들을 모두 다룬 것이다. 이제 다음 글에서부턴 본격적으로 모나드와 관련된 응용 이론들을 알아보자.