title: Haskell label a binary tree through depth-first in-order traversal
body: <p>I need to label a binary tree through depth-first in-order traversal and I figured therefore I'd need to first go through the left branches of the tree and label those, then do the same for the right branches. My binary tree only stores values at the internal nodes (not at end nodes / leaves):</p>
  
  <pre><code>label :: MonadState m Int =&gt; Tree a -&gt; m (Tree (Int, a))
  label (Branch l x r) = do n &lt;- get
                            l' &lt;- label l
                            r' &lt;- label r
                            return (Branch l' (n, x) r')
  label (Leaf) = return Leaf
  </code></pre>
  
  <p>*EDIT: Need to use the State Monad however I'm not really grasping the usage of it. My current code is shown above but is not working properly.</p>
  
  <p>EDIT: The desired result e.g. for:</p>
  
  <pre><code>Branch (Branch Leaf (-2) Leaf) 1 Leaf
  </code></pre>
  
  <p>should be:</p>
  
  <pre><code>Branch (Branch Leaf (0,-2) Leaf) (1,1) Leaf
  </code></pre>
  
  <p>Also I'm not sure how I should use the State Monad for it, I'm still quite confused for its use:</p>
  
  <pre><code>instance Monad (State' s) where
  
      -- return :: a -&gt; State' s a
      return x = State' (\(s,c) -&gt; (x, s, (c &lt;&gt; oneReturn) ))
  
      -- (&gt;&gt;=) :: State' s a -&gt; (a -&gt; State' s b) -&gt; State' s b
      st &gt;&gt;= k = State' $ \(s,c) -&gt; let (a, s', c') = runState' st (s,c)
                                    in runState' (k a) (s',(c' &lt;&gt; oneBind) )
  
  instance MonadState (State' s) s where
  
      -- get :: State' s s
      get = State' $ \(s,c) -&gt; (s,s, (c &lt;&gt; oneGet))
  
      -- put :: s -&gt; State' s ()
      put s = State' $ \(_,c) -&gt; ((),s, (c &lt;&gt; onePut))
  </code></pre>