모나드 만들기

이 글은 책 Learn You a Haskell for Great Good 챕터 14의 Making Monads 섹션을 읽고 정리한 것이다.

보통은 모나드를 만들기 위해서 모나드를 만들기보다는 어떤 문제를 해결하기 위해서 타입을 먼저 만들고 이게 어떤 문맥이 있고 모나드가 될 것 같으면 그때 모나드 인스턴스를 만들면 된다.

리스트와 확률

리스트는 여러개의 값중에 어떤 것이 될지 알 수 없다는 문맥을 가지고 있다. nondeterministic

그런데 이때 리스트는 많은 후보들 중에서 어떤 한 값이 될 가능성이 높고 낮은지에 대한 확률 정보는 가지고 있지 않다. 만약 [3, 5, 9] 중에서 3이 나올 확률은 50%이고 5나 9가 나올 확률은 25%라고 하는 정보를 나타내려면 어떻게 하면 될까?

유리수 타입

하스켈에는 유리수 Rational 타입이 있다. Data.Ratio 모듈을 사용하면 되고 아래와 같이 분자와 분모 사이에 %를 적어주면 된다.

ghci> 1%4
1 % 4
ghci> 1%2 + 1%2
1 % 1
ghci> 1%3 + 5%4
19 % 12

이제 아래와 같이 리스트와 Rational 타입을 이용해서 확률 정보를 표현해보자!

[(3,1%2),(5,1%4),(9,1%4)]

이렇게 놓고 보니 리스트에 확률이라는 어떤 새로운 문맥이 생긴 것 같다. 이제 이걸 타입으로 만들어보자.

Prob 타입

newtype Prob a = Prob { getProb :: [(a, Rational)] } deriving Show

타입 Prob는 과연 functor일까? 원래 리스트가 functor이고 Prob는 거기에 확률만 더한 것이니 Prob도 functor가 맞을 것 같다. 아래와 같이 functor 인스턴스도 만들어보자. 확률 정보는 그대로 두고 리스트 안의 값들에 함수만 적용해주면 된다.

instance Functor Prob where
  fmap f (Prob xs) = Prob $ map (\(x, p) -> (f x, p)) xs

모나드일까?

먼저 return에 대해 생각해보자. return은 어떤 값에 최소한의 문맥을 주는 것이다. 어떤 값에 확률 리스트라는 최소한의 문맥을 줘야한다면 그 값 하나만 들어 있는 싱글톤 리스트에 확률이 100%인 문맥을 주면 될 것 같다.

return x = Prob [(x,1%1)]

이번에는 >>=에 대해 생각해보자. 잘 모를 때는 전에 알아본 것처럼 아래 성질을 이용하면 된다.

m >>= f = join (fmap f m)

join을 어떻게 구현할 수 있을까?

join :: (Monad m) => m (m a) -> m a
join :: Prob (Prob a) => Prob a

확률을 꺼내려면 밖에 있는 확률과 안에 있는 확률을 곱하면 된다. 예를 들어 아래에서 a를 꺼냈을 때 확률은 1%4 * 1%2로 1%8과 같게 된다.

thisSituation :: Prob (Prob Char)
thisSituation = Prob
  [(Prob [('a',1%2),('b',1%2)], 1%4)
  ,(Prob [('c',1%2),('d',1%2)], 3%4)
  ]

join 이라는 함수 이름은 이미 있으니까 아래처럼 flatten이라는 이름으로 join을 구현해보자.

flatten :: Prob (Prob a) -> Prob a
flatten (Prob xs) = Prob $ concat $ map multAll xs
  where multAll (Prob innerxs, p) = map (\(x, r) -> (x, p*r)) innerxs

이제 fmap도 있고 join도 있으니 모나드를 만들 수 있다!

모나드 인스턴스

instance Monad Prob where
  return x = Prob [(x,1%1)]
  m >>= f = flatten (fmap f m)
  fail _ = Prob []