개미 수열 Haskell 풀이

개미 수열 1,11,21,1211,… 을 Haskell로 구현하는데 두 개의 모나드가 사용되었다. 무엇인지 살펴보자.

아래 책에는 Haskell 풀이가 등장한다.

책: 개미 수열을 푸는 10가지 방법

import Data.List
import Control.Monad
ant = iterate(group >=> sequence[length, head])[1]

책은 Haskell을 설명하는 책이 아니기 때문에 이 코드에 대해 자세한 설명은 생략하고 함수 이름들로 대략적인 동작을 설명하고 넘어간다.

ant함수는 첫 줄 [1]을 시작으로 다음 줄 계산 (group >=> sequence[length, head])을 반복 (iterate) 한다. 다음 줄을 계산할 때는, 먼저 앞 줄을 같은 값끼리 묶고 (group), 각 그룹의 길이(length)와 머릿값(head)으로 바꿔치운다.(>=> sequence[])

좋은 코드라고 할 수는 없겠지만 Haskell을 공부하는 사람들에게는 이 코드에 대한 부연 설명이 필요할 것 같아서 이 글로 보충하려고 한다.

코드에서 핵심이 되는 부분은 >=> 연산자와 sequence 를 사용한 부분이다. Haskell을 잘 아는 사람이라면 이 두 함수가 별거 아니겠지만 아직 모나드와 싸우고 있는 Haskell 학습자라면 쉽지 않을 것이다.

>=> 연산자

>=> 연산자는 Kleisli arrow를 합성하는 연산자다. Kleisli arrow는 (Monad m) => a -> m b 타입이라고 보면 된다. 일반적으로 모나드의 합성은 >>= 연산자를 이용하지만 함수 합성이라는 관점에서 보자면 >=> 가 더 직관적이다.

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
(>>=) :: Monad m =>       m a  -> (a -> m b) ->      m b

비교에서 보듯이 >>= 연산자는 a -> 부분이 앞과 뒤에 생략되어 있다. 그래서 사실은 합성을 위한 연산자지만 합성처럼 보이지 않는 것이다.

그러면 개미 수열 코드 group >=> sequence[length, head] 에서는 어떤 모나드가 사용된 것인가? group의 타입이 Eq a => [a] -> [[a]] 임을 알고 있다면 리스트 모나드가 사용된 것을 알 수 있다.

group의 입력 타입을 A([a]), 출력 타입을 [B]([[a]])라고 본다면 sequence [length, head]의 타입은 B -> [C] 라는 것을 알 수 있다. 즉, A -> [B] 와 B -> [C] 가 합성되어 A -> [C]가 되는 셈이다.

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
group ::           [a] -> [[a]]
sequence [length, head] ::       [a] -> [C]
group>=>sequence[length,head] ::              [a] -> [C]

sequence 함수

그럼 sequence[length, head]는 무슨 타입일지 추적해보자.

iterate의 첫번째 인자 타입은 (a -> a) 이므로 [C]는 A와 같은 타입이다. 아까 A는 [a]였으므로 C는 a타입이다. 즉, sequence[length, head]의 타입 B -> [C]는 [a] -> [a]이다.

sequence 는 (Traversable t, Monad m) => t (m a) -> m (t a) 타입을 가진다. 그럼 여기에 사용된 모나드는 무엇일까? 앞에서처럼 리스트 모나드일까?

먼저 Traversable 은 리스트라는 것을 바로 알 수 있다. 그러면 sequence는 [m a] -> m [a] 타입이다. length :: [a] -> Int와 head :: [a] -> a가 같은 타입으로 묶어져야 사용된 모나드를 알 수 있다. a가 Int면 length와 head는 같은 타입 [Int] -> Int가 된다.

[Int] -> Int 타입이 모나드? 그렇다. 함수((->) r)도 모나드가 정의되어 있다.

instance Monad ((->) r) where
    f >>= k = \ r -> k (f r) r

r을 입력으로 가지는 함수는 모나드가 정의되어 있고, 여기서는 r이 [Int]다. sequence는 [m a] -> m [a]이고 [length, head]는 앞서 [[Int] -> Int]타입이라는 것을 확인했으므로, (-> [Int])가 m 부분에 해당하고, a는 Int가 된다. 이것들을 모두 조합하면..

length :: [a] -> Int
head :: [a] -> a
[length, head] :: [[Int] -> Int]
sequence :: [m a] -> m [a]
sequence[length, head] :: [Int] -> [Int]

이렇게 해서 group >=> sequence [length, head] 는 [Int] -> [[Int]] 와 [Int] -> [Int] 가 합성되어 [Int] -> [Int]가 된다. (iterate 의 첫 인자 타입인 a -> a 에 맞는다.)

이렇게 해서 group >=> sequence [length, head] 이 짧은 표현식에 두 가지 모나드(리스트 모나드, 함수 모나드)가 적용되었다.