Monad 3 - Composition, Transformation
Before starting
2편을 통해 우리는 모나드를 제대로 정의하기 위한, 그리고 모나드를 확장하기 위한 기초적인 타입들을 알아봤다. 이번 글에서는 모나드와 관련된 다양한 응용 이론들을 알아볼 것이다.
Kleisli Composition
지난 두 편의 글을 통해서 모나드는 함수형 언어에서 상당히 큰 축을 차지하고 있음을 알게 되었다. 그렇기 때문에 함수의 인자 혹은 리턴값에 모나드가 포함된 경우는 매우 자연스럽고, 또 상당히 많이 보게 된다. 당장 1편에서 모나드를 설명하기 위해 사용했던 로그나 랜덤 함수들도 지금 와서 보면 일반적인 값을 인자로 받아 모나드를 리턴하는 함수들이다.
그런데 함수형 언어에서는 함수를 합성하는 일이 상당히 자주 일어나고, 또 그만큼 중요하다. 당장 1편의 예시도 모나드를 리턴하는 함수를 합성하기 위한 것이었다. 이제 그 고찰을 다시 가져와서, 조금 일반화를 시켜보자.
우선 한 가지 용어를 짚고 넘어가자. 모나드를 리턴하는 함수를 Kleisli Arrow라고 부른다. 보다 구체적으론 다음과 같다.
1
type Kleisli m a b = a -> m b
그리고 일반 함수의 합성과 다르게, 이런 Kleisli Arrow를 합성하는 연산자를 Kleisli Composition이라 부르며, >=> 기호를 사용한다. 일반 함수의 합성과 타입을 비교해보면 좀 더 명확하게 알 수 있다.
1
2
3
(.) :: (b -> c) -> (a -> b) -> (a -> c)
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
<=<는 모양에서 짐작할 수 있듯, 역방향 Kleisli Composition을 뜻한다. 당연히 g <=< f와 f >=> g는 동일하다.
그러면 Kleisli Composition을 어떻게 구현할 수 있을까? Option 모나드에 대해 이걸 직접 구현해보려고 하면 다음과 같은 형태일 것이다.
1
2
3
4
5
6
7
8
let validateParse s =
match tryParseInt s with
| Some x -> validatePositive x
| None -> None
validateParse "42" // Some 42
validateParse "-5" // None
validateParse "abc" // None
역시나 패턴 매칭이다. 그런데 이건 전혀 일반화라고 볼 수 없다. 보다 일반적인, 임의의 모나드에 대해 Kleisli Composition을 어떻게 작성할 수 있을까? 위의 패턴 매칭 구현과, 모나드에서 제공하는 내장 함수들인 fmap, <*>, return, >>=를 잘 비교해보면, 다음과 같이 Bind로 어떻게든 간략화시킬 수 있다는 것을 알 수 있다.
1
let validateParse s = tryParseInt s |> Option.bind validatePositive
여기까지 왔으면 이제 남은 일은 간단하다. validateParse는 tryParseInt와 validatePositive를 합성한 함수이므로, 보다 일반적인 f >=> g는 다음과 같이 쓸 수 있겠다.
1
2
let (>=>) f g = fun x -> f x |> Option.bind g
let (<=<) g f = f >=> g
한 번 정방향을 정의한 후라면, 역방향은 정방향 구현을 이용해서 손쉽게 구현할 수 있다. 물론 위의 구현은 Option 모나드에 대한 것이라고 가정하고 구현되었기에, 실제로 F#에선 모나드마다 별도의 연산자가 필요하다. 이를 자세히 다루는 것은 모나드 자체를 이해하자는 이 글의 범위를 벗어나기 때문에 다른 글에서 자세히 다룰 예정이다. 참고로 하스켈에서는 모나드가 클래스로 정의되어 있기 때문에 Kleisli Composition의 일반적인 형태를 아래와 같이 구현할 수 있다.
1
2
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \x -> f x >>= g
물론 이렇게 정의하지 않아도 함수형 그 자체인 언어답게 하스켈에서 이 정도는 기본적으로 제공하고 있다.
Monad Transformer
우리가 여태까지 본 모든 상황들은 하나의 Type에 대해서 다루고 있다. 위의 Kleisli Composition도 단일 모나드를 리턴하는 두 함수의 합성이다. 그런데 실제 상황에서는 모나드를 하나만 써도 되는 일이 거의 없다. IO 안에서 Maybe를 표현하고 싶거나 F#의 경우 async 안에서 option을 다루고 싶은 경우 등 이러한 상황은 상당히 자주 등장하게 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-- 사용자 입력을 받아 정수로 파싱, 실패 시 Nothing 리턴
readInt :: IO (Maybe Int)
readInt = do
line <- getLine
return (readMaybe line)
-- 위의 readInt를 두번 실행하여 이를 더하는 함수
addInputs :: IO (Maybe Int)
addInputs = do
mx <- readInt
my <- readInt
case mx of
Nothing -> return Nothing
Just x -> case my of
Nothing -> return Nothing
Just y -> return (Just (x + y))
그리고 이러한 IO(Maybe Int) 간의 덧셈을 수행하려면 위와 같이 중첩된 case가 필요해진다. 이거보다 훨씬 더 복잡한 케이스라면 이는 악명높은 JavaScript의 콜백 지옥이랑 다를 바가 없어진다.
왜 이렇게 될 수 밖에 없는 걸까? 우선 Functor, Applicative와는 다르게 모나드는 합성 연산에 대해 닫혀있지 않다. 즉, 두 모나드 M과 N에 대해 M (N a)이 항상 모나드가 된다는 보장이 없다. M (N a)가 모나드가 되기 위해서는 아래의 join 함수가 필요하다.
1
join :: M (N (M (N a))) -> M (N a)
그런데 위의 join 함수를 구현하려면 N (M a) -> M (N a)형태의 변환, 즉 모나드 간의 분배법칙이 성립되어야 한다. 그런데 안타깝게도 임의의 두 모나드에 대해서는 분배법칙도 성립하지 않는다. 그렇기 때문에 위의 개념들을 일반화할 방법이 존재하지 않는다.
여담으로, 위의 내용은 그리 자명하지 않고 논리적 비약도 어느 정도 섞여 있다. 그러나 관련된 모든 이론적 내용을 기술하기엔 글이 너무 길어질 것이고 또한 더 이상 프로그래밍이 아니라 수학적으로 접근해야 하는 내용이라 별도의 포스팅에서 자세하게 다룬다.
각설하고, 그럼 이론적으로 일반화가 불가능하니 항상 위의 예시처럼 case를 중첩해서 쓰라는 얘기일까? 다행스럽게도 그렇지는 않다. 프로그래밍에서 실제로 쓰이는 대부분의 모나드들은 수학적으로는 구조가 간단한 경우가 많아 분배법칙이 대부분 성립한다. 그렇기 때문에 임의의 모나드 쌍에 대해서는 불가능하더라도, 모나드 합성이 가능한 모나드 M이 자신과 임의의 다른 모나드를 합성하는 방법을 제공해주면 꽤 편리하게 쓸 수 있다. 그리고 이 개념을 모나드를 변환해서 새 모나드를 만들어준다는 의미로 Monad Transformer라고 부른다.
구체적으로 다음과 같이 정의된다.
1
newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }
위의 타입 MaybeT는 Maybe를 위한 transformer이며, 임의의 모나드 M 안에 Maybe를 감싼 새로운 모나드를 뜻한다. 즉 IO (Maybe Int) 대신 MaybeT IO Int라고 표현할 수 있다. 별 차이가 없는 것 같지만 이 경우 MaybeT IO가 하나의 모나드가 되기 때문에 모나드 하나를 다룰 때처럼 자유로운 표현이 가능해진다.
그리고 Maybe를 감싼 형태라고 방향이 정해져 있으므로, Maybe (IO Int)는 MaybeT Io Int와는 전혀 다른 타입이다. 이 역시 분배법칙이 성립하지 않아서 그렇다는 것을 염두에 두자.
MaybeT에 대한 인스턴스는 다음과 같이 구현할 수 있다.
1
2
3
4
5
6
7
8
instance Monad m => Monad (MaybeT m) where
return = MaybeT . return . Just
(MaybeT x) >>= f = MaybeT $ do
v <- x
case v of
Nothing -> return Nothing
Just a -> runMaybeT (f a)
>>=를 구현할 때 사용한 do는 m에 대한 do이다. 즉, m이 갖고 있는 side-effect를 처리하면서, 동시에 Maybe의 side-effect를 내장시켜준다. 또한 몇번이나 말했듯 임의의 모나드에 대한 합성은 불가능하기 때문에 각각의 모나드에 대해서 transformer가 따로 정의되어야 한다는 점을 기억해두자.
그럼 이제 이걸 쓰면 어떻게 간단해지는지 위의 코드에 MaybeT를 적용한 코드를 살펴보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import Control.Monad.Trans.Maybe
import Text.Read (readMaybe)
readInt :: MaybeT IO Int
readInt = do
line <- lift getLine
MaybeT . return $ readMaybe line
addInputs :: MaybeT IO Int
addInputs = do
x <- readInt
y <- readInt
return (x + y)
main :: IO ()
main = do
result <- runMaybeT addInputs
case result of
Nothing -> putStrLn "Parsing Failed"
Just n -> putStrLn $ "Sum: " ++ show n
우리의 기대대로 일반적인 모나드처럼 다룰 수 있게 되었다.
그런데 위의 예제에서 readInt 함수가 무슨 일을 하는지 확인해보자. 이 함수는 IO String을 받아서 MaybeT IO String으로 변환한 후, 거기서 꺼낸 String을 MaybeT IO Int로 변환하는 함수다.
즉, IO String -> MaybeT IO String으로 변환하는 함수가 필요하다. 위의 코드에선 이 일을 lift 함수가 해줬는데, 이 함수는 다음과 같이 정의되어 있다.
1
2
class MonadTrans t where
lift :: Monad m => m a -> t m a
즉, 하위 모나드의 효과를 transformer 안으로 끌어올리는 함수라서 이름이 lift인 것이다. 모든 Monad Transformer는 위의 MonadTrans 클래스도 반드시 구현해야 한다.
하스켈에서는 MaybeT, ExceptT, StateT, ReaderT, WriterT와 같은 transformer는 이미 정의되어 있다. 각각 Maybe, Either e, State s, Reader r, Writer w를 감싸게 해주는 타입들이다.
실제로는 위와 같이 2개만 합치지 않고, 여러 개의 transformer를 겹쳐서 사용하는 경우도 많다. 예컨데 IO와 에러 처리, 상태 관리를 모두 하고 싶다면 ExceptT String (StateT Int IO) a라고 스택을 쌓듯이 정의해야 한다. 그리고 IO에서부터 이 모나드 스택까지 끌어올리려면 총 2번의 lift가 필요할 것이다.
이 또한 transformer 스택이 깊어질수록 쓰기 상당히 불편해진다. 하스켈에서는 이를 방지하기 위해 mtl 스타일을 제공한다.
1
2
3
4
5
6
7
8
9
10
11
import Control.Monad.State
import Control.Monad.Except
type AppStack a = ExceptT String (StateT Int IO) a
runApp :: AppStack()
runApp = do
modify (+1)
count <- get
when (count > 5) $ throwError "Counter Exceeded!"
liftIO $ putStrLn $ "Count: " ++ show count
modify와 get이 모나드 스택 중 어느 레이어에서 제공하는 기능인지에 맞춰 수동으로 lift를 하지 않고, 타입 추론에 의존하여 자동으로 처리해준다. 실제로 lift가 필요할 경우는 liftIO를 통해 IO를 AppStack까지 단번에 끌어올려준다.
Natural Transformation
여태까지 봤던 상황들은 전부 모나드를 변환하지 않았다. Transformer 역시도 기반이 되는 Base 모나드는 그대로고, 거기에 다른 모나드를 합성해서 새 모나드를 만드는 방법이었다. 그런데 실제론 모나드 자체를 변환해야 하는 일도 상당히 많다. 똑같이 실패 상황을 다루는데 한쪽은 Maybe를 쓰고, 다른 쪽은 Either를 쓴다거나, 혹은 모나드가 다루고 있는 컨텍스트가 더 이상 필요하지 않고 다른 컨텍스트가 필요해졌다거나 하는 일들은 생각보다 많이 발생한다.
그런데 이러한 문제를 해결하기 위해선, 우리가 지금까지 짚어봤던 개념들로는 좀 부족하다. fmap은 같은 Functor 안에서 값을 변환하는 것이지 Functor 자체를 다른 것으로 바꾸는 기능이 아니고, 이는 Applicative나 모나드도 마찬가지다.
이러한 모나드 간의 변환을 Natural Transformation, 즉 자연 변환이라고 한다. 이는 하스켈로 다음과 같이 표현할 수 있다.
1
type (f ~> g) = forall a. f a -> g a
간단한 natural transformation의 예시는 다음과 같다. 한 모나드를 다른 모나드로 변환하는 것이기에 모든 경우에 대응되는 일반적인 구현은 존재하지 않는다.
1
2
3
4
5
6
7
8
9
-- Maybe -> []
maybeToList :: forall a. Maybe a -> [a]
maybeToList Nothing = []
maybeToList (Just x) = [x]
-- [] -> Maybe
listToMaybe :: forall a. [a] -> Maybe a
listToMaybe [] = Nothing
listToMaybe (x:_) = Just x
여기서 forall 키워드는 뒤의 a가 무엇이든지 상관없이 동일하게 작동해야 한다는 의미의 키워드이다. 직관적으로 생각해봐도, 모나드 자체를 변환하는데 특정 타입만 변환이 된다면 이걸 모나드를 변환했다고 말하긴 힘들 것이다.
보다 엄밀하게 따지자면, 모든 natural trnasformation은 자연성 조건(Naturality Condition)을 만족해야 하는데, 이를 간단하게 하스켈로 표현하면 아래와 같다.
1
fmap f . n = n . fmap f
여기서의 n은 natural transformation이다. 즉, 변환 후 매핑을 한 것과, 매핑 후 변환한 것이 동일해야 한다. 그리고 하스켈에서의 forall 제약이 이를 자동적으로 보장해준다. forall이 걸려있는 함수를 구현할 때, a에 접근하는게 불가능하기 때문에 자연성 조건을 만족할 수 밖에 없다.
Natural transformation도 결국은 함수이기 때문에, 이들끼리도 합성이 가능하다.
1
2
3
4
5
6
7
8
9
-- Vertical Composition
(•) :: (g ~> h) -> (f ~> g) -> (f ~> h)
(g2h • f2g) x = g2h (f2g x)
-- Horizontal Composition
horizontal :: (forall a. f a -> g a)
-> (forall a. h a -> k a)
-> h (f a) -> k (g a)
horizontal fg hk = hk . fmap fg
위와 같이 Vertical Composition과 Horizontal Composition이라는 개념이 존재한다. Vertical composition은 일반 함수 합성과 동일한 개념이며, 실제로 쓰는 것도 동일하다.
Horizontal composition은 Functor도 같이 합성하는 것으로, n: F -> G, e: H -> K라면 H(F) => K(G) 형태로 합성하는 것이다. 이는 위 코드와 같이 fmap을 써서 구현할 수 있다.
그런데 단순 변환을 넘어서, 모나드의 구조까지 보존하는 것을 Monad Morphism이라고 부른다. 이는 아래의 2가지 조건을 추가로 만족해야 한다.
1
2
3
4
5
6
7
-- e: m -> n
-- Return 보존
e (return a) = return a
-- Bind 보존
e (m >>= f) = e m >>= (e . f)
즉, 변환 전 모나드 m과 변환 후 모나드 n의 return, bind가 동일한 동작을 가진다는 의미이다. 구체적으론 다음과 같은 변환 함수 maybeToExcept는 Monad Morphism이 된다.
1
2
3
4
5
6
7
8
9
10
import Control.Monad.Trans.Maybe
import Control.Monad.Trans.Except
-- MaybeT -> ExceptT
maybeToExcept :: forall a. String -> MaybeT IO a -> ExceptT String IO a
maybeToExcept errMsg (MaybeT action) = ExceptT $ do
result <- action -- run IO (Maybe a)
return $ case result of
Nothing -> Left errMsg
Just x -> Right x
여기까지 보면 앞에서 다룬 Monad Transformer와 Natural Transformation은 딱히 상충되는 개념이 아님을 알 수 있다. 그러면 Transformer의 기반이 되는 모나드를 자연 변환을 이용해 교체해버리는 것도 가능하지 않을까? 실제로 가능하고, 이를 “hoist”라고 부른다.
1
2
3
4
hoist :: (MFunctor t, Monad m)
=> (forall a. m a -> n a)
-> t m b
-> t n b
여기서 Mfunctor는 타입 생성자 수준의 fmap으로, 다음과 같이 정의된다.
1
2
class MFunctor t where
hoist :: Monad m => (forall a. m a -> n a) -> t m b -> t n b
이렇게 hoist를 하게 되면, Transformer의 껍데기를 유지하면서, base 모나드만 교체할 수 있다. hoist 자체는 임의의 자연 변환으로 교체가 가능하지만 이 변환이 Monad morphism이라면 모나드의 구조까지 보존된다는 보장을 얻을 수 있다.