Graphics Programming

[번역] The State Monad: A Tutorial for the Confused? 본문

Season 1/하스켈

[번역] The State Monad: A Tutorial for the Confused?

minseoklee 2015. 10. 2. 20:18

원문: http://brandon.si/code/the-state-monad-a-tutorial-for-the-confused/

 

원작자 Brandon Simmons의 허락을 받아 번역한 글입니다. 원글의 라이센스는 Creative Commons BY-NC-SA로서 저작자 표시, 비영리, 동일조건변경허락 제약이 걸려있습니다.

 

하스켈의 State 모나드에 대한 이 튜토리얼은, 내가 읽었던 다른 글들에서 직면한 알기 어려웠던 차이점들을 이해하고, 모든 난해한 추상화를 파헤치기 위해 작성한 것이다. 이 글은 Maybe 모나드와 List 모나드는 잘 이해했지만 State 모나드에서 턱 막힌 사람들을 위한 것이다. 도움이 되기를!

 

데이터 선언

모나드를 이해하려면 그것의 자료형과 bind(>>=)의 정의를 살펴봐야 한다. 대부분의 모나드 튜토리얼은 State s a의 자료형 선언을 설명이 필요 없다는 듯이 언급만 한다.

 

newtype State s a = State { runState :: s -> (a, s) }

 

하지만 여기엔 설명이 필요하다! 이것은 List 모나드나 Maybe 모나드에서는 전혀 볼 수 없던 개념이다.

 

1. Maybe의 Just 같은 단순한 값과 달리, 생성자 State는 이상하게도 함수를 보관한다.

2. 게다가 묘하게 명령형 언어의 것처럼 명명된 runState라는 접근자 함수가 있다.

3. 마지막으로, 좌변에는 자유 변수가 한 개가 아니라 두 개가 있다.

 

집중해서 그 실체를 밝혀보자.

 

무엇보다도 State 모나드는 단지, 상태를 취해 중간 값과 새로운 상태 값을 반환하는 함수를 추상화한 것이다. 하스켈에서 이 추상화를 공식으로 나타내기 위해 우리는 그 함수를 newtype State로 감싸고, Monad 클래스의 인스턴스를 정의하는 것이 가능해진다.

 

추상과 개념으로부터 한 걸음 물러나서 보면 State 생성자는 함수 :: s -> (a, s) 의 컨테이너 역할을 한다. 한편 bind의 정의는 함수 state -> (val, state) 를 State 래퍼 내에서 "합성하는" 메커니즘을 제공한다.

 

(+1) . (*3) . head :: (Num a) => [a] -> a 와 같이 함수들을 (.) 로 연결할 수 있는 것처럼, 상태 모나드의 (>>=) 는 :: a -> s -> (a,s) 형태의 함수들을 하나의 :: s -> (a,s) 함수로 연결해준다.

 

위의 논의를 실제 코드로 옮겨서 세 가지 문제를 이해했는지 확인해보자. 다음은 우리의 state 타입에 "포함될 수 있는" 함수의 예시다.

 

-- 카운터를 살펴보고 "foo" 또는 "bar"를 반환한다

-- 그리고 카운터를 증가시킨다

fromStoAandS :: Int -> (String,Int)
fromStoAandS c | c `mod` 5 == 0 = ("foo",c+1)
               | otherwise = ("bar",c+1)

 

이 함수를 State 생성자로 감싸면 우리는 State 모나드 내부로 들어온 것이다.

 

stateIntString :: State Int String
stateIntString = State fromStoAandS

 

그러면 runState는 무엇일까? 이것이 하는 일은 물론 State 생성자의 "내용물"을 우리에게 주는 것이다. 그 내용물은 하나의 함수 :: s -> (a,s) 이다. 이름을 stateFunction이라고 할 수도 있었겠지만, 누군가가 이런 식으로 작성하는 것이 아주 영리할 것이라 생각했나 보다.

 

runState stateIntString 1

 

runState를 사용해 우리의 함수 fromStoAandS를 State 래퍼로부터 빼낸다. 그리고 초기 상태 1을 적용한다. 이 runState 작업은 함수들을 (>>=), mapM 같은 것으로 합성한 후에 수행할 것이다.

 

하지만 문제 3은 아직 대답이 되지 않았다. 이제 State의 인스턴스 선언을 탐구해보자.

 

인스턴스 선언

첫 번째 줄부터 시작한다.

 

instance Monad (State s) where

 

State가 아니라 (State s)의 Monad 인스턴스를 만든다. 이를 부분 적용 함수(partially-applied function)와 동등한, 부분 적용 타입(partially-applied type)으로 봐도 좋다.

 

(State)     <==> (+)
(State s)   <==> (1+)
(State s a) <==> (1+2)

 

그러니까 모나드의 m a에서 m은 (State s)인 것이다. 이는 상태의 타입은 (>>=)로 함수들을 합성해도 그대로 남지만, 중간 값들(a들)은 함수 연결고리를 따라 타입이 변할 수도 있음을 뜻한다.

 

인스턴스 선언의 몸체를 보기 전에, 다음을 숙지하면 return과 (>>=)의 선언을 쉽게 이해할 수 있을 것이다.

 

여러분이 m a를 볼 때,

 

return :: (Monad m) => a -> m a

 

m a는 실제로는 다음과 같다는 것을 기억하라.

 

State s a

 

그리고 (State s a)는

 

(s -> (s,a))

 

임을 떠올리자. 즉, 여러분이 보는 모든 m a는 function :: s -> (a,s) 인 것이다. State 래퍼는 잊어버려라. 컴파일러도 그렇게 한다!

 

return과 bind의 정의

return 정의부터 시작한다.

 

return a = State $ \s -> (a, s)

 

return이 하는 일은 어떤 값을 취해 새로운 함수를 만드는 것인데, 이 함수는 상태값을 취해 (값, 상태값)을 반환한다. State 래핑을 무시하면 return은 단순히 (,) :: a -> b -> (a, b) 이다.

 

이제 bind의 정의를 떠올려보자.

 

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

 

우리의 경우에는

 

(>>=) :: State s a        ->
         (a -> State s b) ->
         State s b

 

이것은 단지 다음의 함수 합성을 추상화한 것이다.

 

(>>=) :: (s -> (a,s))      ->
         (a -> s -> (b,s)) ->
         (s -> (b,s))

 

즉 (>>=) 의 좌변은 어떤 초기 상태를 취해 (value, new_state)를 만들어내는 함수다. 우변은 어떤 값과 new_state를 취해 자신의 (new_value, newer_state)를 만들어내는 함수다. bind의 역할은 단순히 두 함수를 합성하여, 초기 상태로부터 (new_value, newer_state)를 얻어내는 하나의 함수를 만드는 것이다. 단순한 함수 합성 연산자인 (.) :: (b -> c) -> (a -> b) -> a -> c 처럼 말이다.

 

이제 bind의 정의를 보여줄 수 있겠다.

 

m >>= k = State $ \s -> let (a, s') = runState m s
                         in runState (k a) s'

 

여기서 하고 있는 것이 함수 합성임을 인지하고 있다면 스스로 이해할 수 있을 것이다. 중요한 것은 State 바로 다음의 s는, 우리가 함수를 runState로 언래핑하여 초기 상태값을 제공하여 전체 고리를 평가하기 전에는, 바인딩되지 않는다는 것이다.

 

State 모나드의 do 표기에 대한 마지막 노트

State는 이런 식으로 사용되곤 한다.

 

stateFunction :: State [a] ()
stateFunction = do x <- pop
                   pop
                   push x

 

위의 함수들은 m >>= \a-> f... 또는 이전 줄에 왼쪽 화살표가 없다면 m >>= \_-> f... 로 치환된다는 것을 기억하라. a는 튜플의 fst인 중간값이다. push 함수는 다음과 같다.

 

push :: State [a] ()
push a = State $ \as -> (() , a:as)

 

push는 의미있는 a 값을 반환하지 않기 때문에 <- 를 이용하여 바인딩하지 않는다. do 표기에 대한 더 많은 것은 Bonus의 글을 보라.

 

일반화: StateT와 MonadState

자, 이제 여러분은 State 모나드 전문가다. 불행히도 (사실은 좋은 일이다) 내가 위에서 말한 State 타입은 표준 라이브러리에 없다. 대신 State는 여기에서 StateT 모나드 변환기를 이용하여 정의된다.

 

type State s = StateT s Identity

 

모나드 변환기를 본 적이 없다면 StateT s Identity가 어떻게 State s와 같은지 밝혀내려고 해볼 것. 위의 hackage 링크를 따라가보자.

 

역시 mtl 패키지에 있는, MonadState라는 타입클래스도 봤는지 모르겠다. 이렇게 생긴 녀석인데, 이상한 부분부터 설명하겠다.

 

class Monad m => MonadState s m | m -> s where
    get :: m s
    put :: s -> m ()

 

위에서는 구체적인 자료형인 State에 대해 말했는데, MonadState는 모나드인 타입들을 위한 타입클래스이고 get과 put 연산을 정의할 수 있다.

 

MonadState는, 기본적인 상태 연산들을 위한 일반 인터페이스를, 상태 전달을 이용해서 공유하는 다양한 모나드 변환기를 "차곡차곡 쌓을 수 있게" 한다.

 

곁가지: get과 put을 MonadState의 메서드가 아니라 우리의 State 타입의 함수로 정의한다면 이렇게 된다.

 

-- return the state value being passed around:
get :: State s s
get = State $ \s -> (s,s)


-- replace the current state value with 's':
put :: s -> State s ()
put s = State $ \_ -> (s,())

 

썩 괜찮다. 이제는 이것들이 어떻게 작동하는지 이해가 되는가? 그렇다면 State를 더 잘 이해한 것이다. 연습문제: modify :: (s->s) -> State s () 를 정의해볼 것.

 

MonadState로 돌아와서, 이 클래스와 그 인스턴스들이 여러분을 혼란스럽게 한다면, 하스켈98에 추가된 두 가지 확장기능을 알아야 한다. (둘 다 이제는 아주 흔하게 쓰인다) 바로 다중매개변수 타입클래스(Multi-Parameter Type Class)와 함수형 의존성(Functional Dependency)이다.

 

GHC에서 소스코드 맨 위에 다음을 입력하여 두 확장기능을 켤 수 있다.

 

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}

 

다중매개변수 타입클래스

MonadState에서 함수형 의존성(별칭 "fundep")을 무시하면

 

class Monad m => MonadState s m where

 

인데,

 

- MonadState는 클래스 이름이다.

- s는 첫 번째 클래스 타입 변수다(이 경우는 상태의 타입)

- m은 두 번째 타입 변수다(상태류의 모나드의 타입. 예를 들면 State s)

 

다중매개변수 타입클래스는 타입간 관계를 정의한다는 점에서 다소 교묘하다. 이에 대해서는 GHC 문서를 참고할 것.

 

함수형 의존성

하나의 클래스에 매개변수가 여럿이면 그 애매함 때문에 인스턴스가 허용되지 않거나 사용하기 어렵게 될 수 있다. 함수형 의존성은 특정 타입 매개변수를 다른 매개변수들로부터 결정할 수 있음을 명시하는 방법으로, 그 애매함을 해결해준다.

 

MonadState의 경우, 클래스 정의에서 그 부분은

 

| m -> s

 

인데, 이는 m의 타입(예를 들면 StateT Int IO)이 s의 타입(Int)을 유일하게 결정한다는 뜻이다. 자세한 것은 역시 GHC 문서를 참고할 것. Collects 예제가 MonadState와 매우 비슷하다.

 

종합하면 MonadState 클래스 선언을 이렇게 읽을 수 있다.

 

MonadState 클래스에서 m의 타입은 s의 타입을 유일하게 결정하는 관계다.

 

State에 대한 MonadState 인스턴스

마지막으로 다음은 우리가 이 글에서 정의한 State 타입의 MonadState 인스턴스다. (다시 말하지만, State는 mtl에 없는데, 더 일반적인 StateT가 있기 때문이다)

 

instance MonadState s (State s) where
    get = State $ \s -> (s,s)
    put s = State $ \_ -> (s,())

 

 

Comments