상태 모나드를 사용하여 계승 및 피보나치 구현하기 (학습 운동)

Question

Mike Vanier's monad tutorial (우수)을 통해 진행했으며 how to use a "State" monad에 자신의 게시물에서 연습 중 몇 가지를 진행하고 있습니다.

특히 그는 모나드를 사용하여 factorial 및 fibonacci의 쓰기 기능으로 구성된 연습을 제안합니다. 나는 그것을 한방에줬고 아래의 답을 찾았다. (나는 do이라는 표기법을 사용하기 때문에 혼동을 일으킬 수밖에 없다.

나쁜 구현을 내재화하지 않기 위해 "Haskell-y"를 특별히 구현하지는 않았지만 사람들에게 이러한 기능을 구현하는 방법에 대한 의견을 묻습니다 (state 모나드). 이 코드를 훨씬 간단하게 작성할 수 있습니까? (예 : do 표기법으로 변경)? 나는 이것이 사실이라고 생각한다.

---

는 나는이 목적을 위해 state 모나드를 사용하는 실용적 조금 있다고 알고 있어요 그러나 이것은 순전히 학습 운동입니다 - 말장난 가장 확실 구성.

성능은 그다지 나쁘지 않습니다. 100000의 계승을 계산하기 위해 (응답은 ~ 21k 자리입니다), unfoldr 버전은 ~ 1.2 초 (GHCi에서) ~ 1.5 초가 걸렸습니다. 상태 모나드 버전.

import Control.Monad.State (State, get, put, evalState) 
import Data.List (unfoldr) 

fibonacci :: Integer -> Integer 
fibonacci 0 = 0 
fibonacci n = evalState fib_state (1,0,1,n) 

fib_state :: State (Integer,Integer,Integer,Integer) Integer 
fib_state = get >>= 
      \s -> 
       let (p1,p2,ctr,n) = s 
       in case compare ctr n of 
        LT -> put (p1+p2, p1, ctr+1, n) >> fib_state 
        _ -> return p1 

factorial :: Integer -> Integer 
factorial n = evalState fact_state (n,1) 

fact_state :: State (Integer,Integer) Integer 
fact_state = get >>= 
      \s -> 
       let (n,f) = s 
       in case n of 
         0 -> return f 
         _ -> put (n-1,f*n) >> fact_state 

------------------------------------------------------------------- 
--Functions below are used only to test output of functions above 

factorial' :: Integer -> Integer 
factorial' n = product [1..n] 

fibonacci' :: Int -> Integer 
fibonacci' 0 = 1 
fibonacci' 1 = 1 
fibonacci' n = 
    let getFst (a,b,c) = a 
    in getFst 
    $ last 
    $ unfoldr (\(p1,p2,cnt) -> 
       if cnt == n 
        then Nothing 
        else Just ((p1,p2,cnt) 
          ,(p1+p2,p1,cnt+1)) 
      ) (1,1,1) 

Answer 1

귀하의 기능이 조금 복잡해 보이지만 올바른 생각을 가지고 있습니다. 계승을 위해, 계속 추적해야 할 것은 현재 곱한 숫자와 지금까지 누적 한 숫자입니다.

fact_state :: State Int Int 
fact_state = get >>= \x -> if x <= 1 
          then return 1 
          else (put (x - 1) >> fmap (*x) fact_state) 

factorial :: Int -> Int 
factorial = evalState fact_state 

Prelude Control.Monad.State.Strict Control.Applicative> factorial <$> [1..10] 
[1,2,6,24,120,720,5040,40320,362880,3628800] 

피보나치 시퀀스는 유사하다 : 그래서, 우리는 State Int Int은 국가의 현재 번호를 운영하고 있으며 지금까지 곱 한 수를 반환하는 계산이라고 말할 수 있습니다. 함께 추가 할 항목과 지금까지 얼마나 멀리 갔는지 알기 위해 마지막 두 숫자를 유지해야합니다.

fibs_state :: State (Int, Int, Int) Int 
fibs_state = get >>= \(x1, x2, n) -> if n == 0 
            then return x1 
            else (put (x2, x1+x2, n-1) >> fibs_state) 

fibonacci n = evalState fibs_state (0, 1, n) 

Prelude Control.Monad.State.Strict Control.Applicative> fibonacci <$> [1..10] 
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55] 

Answer 2

두 문체 제안 :

 \s -> 
      let (p1,p2,ctr,n) = s 
      in ... 

은 동등하다 :

 \(p1,p2,ctr,n) -> ... 

및 fib_state에 대한 case 문은 if 문으로 기록 될 수 있습니다 :

 if ctr < n 
      then put (p1+p2, p1, ctr+1, n) >> fib_state 
      else return p1