Reverse State 모나드 - 교차 재귀 끝판왕 (작성 중)

(아직 작성 중)

생각 스트레칭

교차 재귀를 읽는 연습
“Programming in Haskell - Graham Hutton”에서 발췌

even :: Int -> Bool
even 0       = True
even n = odd (n - 1)

odd :: Int -> Bool
odd 0       = False
odd n = even (n - 1)

even은 odd를 부르고, odd는 even을 부릅니다. 종료 조건이 없다면 무한히 부를 겁니다. 이런 재귀들은 실용적이려면 어떻게든 종료하는 방법이 필요합니다.

1. 종료되는 조건으로 향해 가든,
2. 무한한 것 중 지정 개수만 가져오든,
3. 종료되는 함수를 넘겨 주든

해야합니다. 마지막 3번째가 낯선 분이 많을 것 같은데요. Reverse State Monad가 이 방법을 씁니다. (처음 읽을 때, 종료 조건이 안보여 이 건 뭐지 했습니다.)

Reverse State 모나드

newtype RState s a = RState { runRState :: s -> (a,s) }

instance Monad (RState s) where
    return x = RState $ (,) x
    RState sf >>= f = RState $ \s ->
        let (a,past) = sf future
            (b,future) = runRState (f a) s
        in (b,past)

rget = RState $ \s -> (s,s)
rmodify f = RState $ \s -> ((),f s)
rput = rmodify . const

execRState f s = snd (runRState f s)

Reverse State Monad - 서광열

1. RState bind를 읽으려고 하면 아무리 Lazy로 읽어도(odd, even 교차 호출 읽듯이) 읽히지 않는다. 특정 형태의 s -> (a, s) 가 있어야 될 것 같다.
2. State가 평가 되려면 결국 rget, rmodify, rput을 만나야 한다.
3. 이들을 넣어서 읽으면 비로소 읽힌다.

Lazy한 것들도 손으로 풀면서 쫓아가면 종료 컨디션이나, 일부분만 평가할 필요가 있거나 하는 식으로 파악이 되는데, 위 RState 바인드는 애초에 아무 s -> (a, s) 가 들어온다고 생각하고 읽으면 돌아가는 모양이 눈에 안들어 옵니다. 무한히 교차 호출이 일어나기만 하고, 이 걸 나중에 어떤식으로 쓸 수 있을지 파악이 안됩니다.

rput을 넣은 다음, rmodify몇 번하고 rget을 넣으면, 동작이, 언젠가 들어올 State에다 계속 함수를 적용해 놓는 모양이 됩니다. 마치 아래 같은 모양이요.

\s -> (+1) . (+2) . (+3) $ s

그래서 미래의 s에 모아 두었던 함수를 내리 적용하게 됩니다. rput도 rget도 넣지 않으면 그냥 무한 교차 재귀일 뿐입니다.

무한 교차 재귀 구조를 만들어 놓고, 당장은 종료 컨디션이나, 필요한 부분이 알려져 있지 않지만, 교차 재귀를 할 때 필요한 함수로 뭘 넣느냐에 따라 의미있는 값이 나오는 구조입니다. 그러는 와중에 값은 각 단계의 effect에 의존하며 값이 바뀌니 그야말로 과거와 미래가 짬뽕된 느낌입니다.

State 모나드와의 차이

과거와 미래

쓸모