Monadic Fibonacci 이해

Question

저는 haskell 및 학습 모나드를 배우고 있습니다. 다음에

import Control.Monad.State 
fib n = flip evalState (0,1) $ do 
    forM [0..(n-1)] $ \_ -> do 
    (a,b) <- get 
    put (b,a+b) 
    (a,b) <- get 
    return a 

내 질문 종기 아래 : 내가 지켜 다양한 튜토리얼을 읽고 상태 모나드에 대한 몇 가지 간단한 예제를 코딩 한, 그러나 나는 (하스켈 위키에서 가져온) 다음 코드 조각을 이해할 수 없습니다입니다 :

1. 무엇이 내면의 첫 번째 문장 안에 들어가는 지, 즉 (a,b)<-get의 결과는 무엇입니까? 몇 가지 구체적인 예를 들면 a 및 b의 값은 무엇입니까?
2. 왜 여기에 상태 모나드를 사용 하시겠습니까?

Answer 1

이 예에서 상태는 시퀀스에서 생성 된 이전 두 숫자를 포함하는 쌍입니다. 이것은 처음에 에 제공된 (0, 1)입니다.

get의 유형

(a, b) <- get 

상태가 쌍을 가져 각각 제 1 및 제 2 요소들과 ab 결합 내측 do 블록 그래서 MonadState s m => m s이다. 상태는 다음 put에서 업데이트됩니다.

상태 따라서됩니다

(a, b) <- get 
return a 

최종 상태 값을 풀어서 제 요소를 반환

(0, 1), (1, 1), (1, 2), (3, 2), (3, 5), ... 

외부.

Answer 2

먼저 피보나치 알고리즘이 사용됨을 확인하십시오. 아이디어는 튜플 (0, 1)에서 시작하여 다음을 (1, 0 + 1), 다음을 (1, 1 + 1), (2, 2 + 1), (3, 3 + 2) 등으로 찾습니다. 일반적으로이 단계는 \(a, b) -> (b, a + b)입니다. 이 튜플에는 피보나치 수를 볼 수 있습니다.

첫 즉 내부 DO의 성명, 어떤 (A, B) <에 결과를 -get 않습니다 내부에 무슨 일

?

하스켈은 문장만을 가지고 있습니다.

y <- x은 완전한 표현식이 아닙니다. x >>= \y ->과 유사합니다.

y <- x 
m 

완전한 표현식은 x >>= \y -> m과 동일합니다. y <- n 형식이 아닌 n 줄은 _ <- n (let 줄을 제외하고 다른 일부는 내가 잊지 않음)와 동일합니다.

이것을 사용하여 우리는 표기 할 수 있습니다.

fib n = 
    flip evalState (0, 1) 
    (forM 
     [0..(n-1)] 
     (\_ -> get >>= (\(a, b) -> put (b, a + b))) 
    >>= (\_ -> get >>= (\(a, b) -> return a))) 
) 

지금 그것은 단지 등 이해 >>=, return, get, put 및에 관한 것입니다.

상태는 실제로는 s -> (s, a) 유형의 기능입니다. 그들은 초기 상태를 취하고 다음 상태에 다른 값을 더합니다.

m >>= n a.k.a "bind"는 Monad m => m a -> (a -> m b) -> m b 유형입니다.

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

m에 의해 반환 a가 가지고있는이 n에 전달 될 : 우리의 모나드가 State s 인 경우,이 동일합니다. 다른 무엇을 추측 할 수 있습니까? 우리는 주정부도 통과 할 것으로 예상하므로 m으로 반환되는 주정부는 n으로 전달되어야합니다. m >>= n 함수는 n이 반환하는 상태와 값을 반환해야합니다.

return = flip (,) 

get :: State s s이 get :: s -> (s, s)에 해당합니다 :

get = join (,) 

put :: s -> State s() 또는 put :: s -> s -> (s,()) :

다음 return :: a -> s -> (s, a)에 해당

m >>= n = uncurry (flip n) . m 

return :: Monad m => a -> m a : 우리는 다음 바인딩을 구현하는 방법을 알고

put s _ = (s,()) 

evalState :: s -> State s a -> a 또는 evalState :: s -> (s -> (s, a)) -> a :

evalState s f = snd (f s) 

당신은 모든 정의를 확장하여 예에서 일어나는 정확하게 볼 수 있습니다. 그러나 직감만으로도 충분합니다.

forM 
    [0..(n-1)] 
    (\_ -> get >>= (\(a, b) -> put (b, a + b))) 

우리는 숫자 때문에 첫 번째 인수가 삭제됩니다 n - 1-0를하는 것에 대한 걱정하지 않는다. get은 현재 상태를 검색하고 put은 새 상태를 씁니다. 우리는 이것을 n 번합니다.

>>= (\_ -> get >>= (\(a, b) -> return a))) 

누적 값 (단위)이 중요하지 않으므로 첫 번째 매개 변수가 삭제됩니다. 그런 다음 현재 상태를 가져 와서 쌍의 첫 번째 요소 만 투사합니다. 이것이 우리가 찾고있는 최종 답입니다.

flip evalState (0, 1) … 

마지막으로 (0, 1)부터 시작하여 실행합니다.

이 구현에는 몇 가지 정리가 있습니다. 첫째, 우리는 범위 [0..(n-1)]에 대해 신경 쓰지 않습니다. 우리는 단지 n 번 작업을 반복하는 것에 관심이 있습니다.이 작업을 수행하기위한보다 직접적인 방법은 다음

replicateM n (get >>= \(a, b) -> put (b, a + b)) 

결과입니다 미사용 단위의 목록, 그래서 더 효율적인 버전이 : 이미있는 기능

replicateM_ n (get >>= \(a, b) -> put (b, a + b)) 

있다

은 get에 이어 put이라는 공통 패턴이 있으며 modify이라는 이름으로 \f -> get >>= put . f으로 정의됩니다. 따라서 :

replicateM_ n (modify (\(a, b) -> (b, a + b))) 

는 그런 부분이 :

>>= (\_ -> get >>= (\(a, b) -> return a))) 

우리가 >>을 사용할 수 있습니다 이전 결과에 대해 걱정하지 않는 모든 시간.

>> get >>= (\(a, b) -> return a)) 

입니다 :

>> get >>= return . fst 

m >>= return . f 단순화 fmap f m에 : 이제

>> fmap fst get 

우리가, 총 :

fib n = 
    evalState 
    ( replicateM_ n (modify (\(a, b) -> (b, a + b))) 
    >> fmap fst get 
) 
    (0, 1) 

우리는 또한 비교를 위해 사용할 수 :

fib = 
    fst 
    . flip evalState (0, 1) 
    . (>> get) 
    . flip replicateM_ (modify (snd &&& uncurry (+))) 

가 왜 여기 상태 모나드를 사용하고자하는 것 :

fib n = 
    fst 
    (evalState 
    ( replicateM_ n (modify (\(a, b) -> (b, a + b))) 
    >> get 
    ) 
    (0, 1) 
) 

그리고 내가 바보이기 때문에

?

그렇지 않을 수도 있습니다. 이것은 상태 값만 사용하기 때문에 분명합니다. 다른 값은 항상 단위이며 버려집니다. 즉, 처음에는 n (즉 피보나치 수를 찾을 필요가 있습니다) 만 있으면 누적 튜플 만 있으면됩니다.

때로는 h . g . f과 같은 구성 문자열이 있다고 생각하지만 한 개 대신 두 개의 인수를 보내려는 경우가 있습니다. 즉, State이 적용될 수 있습니다.

일부 함수가 읽히고 일부 (두 번째 인수)의 상태를 쓰거나 두 가지 모두를 수행하면 State이 계산서에 적합합니다. 독자 만있는 경우 Reader을 사용하고 작성자 만있는 경우 Writer을 사용하십시오.

State Monad를보다 잘 활용하기 위해이 예를 변경할 수 있습니다. 튜플을 사라지게 만들거야!

fib = 
    flip evalState 0 
    . foldr (=<<) (return 1) 
    . flip replicate (\x -> get >>= \y -> put x $> x + y) 

Answer 3

그래서 문서 상태 : get :: m s -- Return the state from the internals of the monad (here 참조).

그러나 저는 주 모나드 (State Monad)에서 머리를 감싸려고 할 때 이것이 많이 도움이되지 않았 음을 기억합니다.

ghci에서 :i 및 :t으로 재생하고 다른 하위 표현을 테스트하는 것이 좋습니다. 그냥 그것에 대한 느낌을 얻을 수 있습니다. 이 같은 비트 :

import Control.Monad.State.Lazy 

runState (get) 0 
runState (get >>= \x -> put (x+1)) 0 
:t return 1 :: State Int Int 
runState (return 1) 0 
runState (return 1 >>= \x -> (get >>= \y -> return (x+y))) 0 

-- Keeping a pair of (predecessor/current) in the state: 
let f = (get >>= (\(a,b) -> put (b,a+b))) :: State (Int, Int)() 
runState (f >> f >> f >> f >> f >> f) (0,1) 

-- only keeping the predecessor in the state: 
let f x = (get >>= (\y -> put x >> return (x+y))) :: State Int Int 
runState (return 1 >>= f >>= f >>= f >>= f >>= f >>= f) 0 

또한 modify, runState, evalState, execState 함께 놀러.