수정 모나드 상태

Question

프로그래밍 연습에서는

이, 내가 데이터 유형

data Tree a = Branch (Tree a) a (Tree a) | Leaf 
    deriving (Eq, Ord, Show) 

의 트리를 가지고와 Int 각 a 레이블을 가정하고, 점점 더 깊이 우선의 순서, 상태 모나드를 사용하여, 모나드 행위의 수를 센다. 여기

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

내 label의 구현 및 run

label :: MonadState m Int => Tree a -> m (Tree (Int, a)) 
label Leaf      = return Leaf 
label (Branch left value right) = do 
            newLeft <- label left 
            int <- get 
            put (int + 1) 
            newRight <- label right 
            return (Branch newLeft (int, value) newRight) 


run :: State' s a -> s -> (a, Counts) 
run s ns = let (a, _, counts) = runState' s (ns, Counts 0 0 0 0) in (a, counts) 

있습니다 : 예를 들어, 표현

let tree = Branch (Branch Leaf "B" Leaf) "A" Leaf 
in run (label tree) 42 

는

(Branch (Branch Leaf (42, "B") Leaf) (43, "A") Leaf 
, Counts {binds = 10,returns = 5, gets = 4, puts = 2}) 

에 국가의 유형은 평가해야 내가 테스트 케이스를 실행할 때

그러나, 나의 결과는

(Branch (Branch Leaf (42,"B") Leaf) (42,"A") Leaf 
, Counts {binds = 12, returns = 5, gets = 6, puts = 2}) 

그것은 전혀 업데이트되고 있지 않은 Int을 것입니다. 할당의 각 부분에 대해 별도의 테스트 케이스가 있기 때문에 이는 이상합니다.이 부분을 제외한 모든 부분은 정확합니다. 어쨌든 여기에 get 및 put 구현이 있습니다.

-- get :: State' s s 
get = State' (\(s, counts) -> (s, s, counts <> oneGet)) 

-- put :: s -> State' s() 
put x = State' (\(x, counts) -> ((), x, counts <> onePut)) 

정말 실망합니다. Int이 전혀 영향을받지 않는 이유를 모르겠습니다. 어떤 도움이라도 대단히 감사합니다.

Answer 1

문제는 당신이 상태로 x을 넣어 야지,하지만이 (x, counts) 패턴에 그림자가됩니다 여기

put x = State' (\(x, counts) -> ((), x, counts <> onePut)) 

입니다. 확인이

put x = State' (\(_, counts) -> ((), x, counts <> onePut)) 

당신이 그들을 위반하여 태스크 포스 때문에, 모나드 법에 대해 걱정하지 않는 한 당신은만큼 잘해야한다 :

는 모나드 행동의 수를 계산

법률 중 하나는 (return x >>= f) ~ f x이지만 이전 표현식에는 return 및 (>>=)이 추가로 포함되어 있습니다.

Answer 2

나는 임무를 알고 있지만, GHC가이 코드를 거의 전부 작성할 수 있다고 지적하고 싶습니다. 마법의 단어는 deriving Traversable입니다.

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-} 
data Tree a = Leaf 
      | Node (Tree a) a (Tree a) 
      deriving (Functor, Foldable, Traversable) 

Traversable 클래스 구조의 각 요소에서 동작을 수행하는 개념을 추상화한다. traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)은 a 요소에 Applicative 효과를 수행하고 t 전체 구조를 통해 실행하여 Applicative 컨텍스트에서 효과를 시퀀싱하는 함수를 사용합니다.

그래서 우리가해야 할 일은, 하나의 요소에 따라 행동하는 방법을 말한다

inc :: a -> State Int (Int, a) 
inc x = do 
    counter <- get 
    put (counter + 1) 
    return (counter, x) 

하고 Traversable 기계는 전체 트리에 걸쳐 작업을 실행하는 무거운 할 것입니다.

label :: Tree a -> Tree (Int, a) 
label t = evalState (traverse inc t) 0 

Node 생성자의 레이아웃은 순회 순서를 결정한다; 이 경우 traverse은 순서 순회를 수행합니다.