title: How to put mutable Vector into State Monad
body: <p>I wrote small program in haskell to count all ocurences of Int values in Tree using State Monad with Vector:</p>
  
  <pre><code>import Data.Vector
  import Control.Monad.State
  import Control.Monad.Identity
  
  data Tree a = Null | Node (Tree a) a (Tree a) deriving Show
  main :: IO ()
  main = do 
      print $ runTraverse (Node Null 5 Null)
  
  
  type MyMon a = StateT (Vector Int) Identity a
  
  runTraverse :: Tree Int -&gt; ((),Vector Int)
  runTraverse t =  runIdentity (runStateT (traverse t) (Data.Vector.replicate 7 0))
  
  traverse :: Tree Int -&gt; MyMon ()
  traverse Null = return ()
  traverse (Node l v r) = do
      s &lt;- get
      put (s // [(v, (s ! v) + 1)]) -- s[v] := s[v] + 1
      traverse l
      traverse r
      return ()
  </code></pre>
  
  <p>But 'update' of immutable Vectors is done in O(n) complexity.
  And I am looking for update in O(1) and access in O(1).
  As I understand Mutable Vectors do what I want. To use them I need to use ST or IO.
  Because I would like to do some UnitTests I prefer ST monad, but I don't want to have to pass that vector around in function calls.
  I need to keep using Monad Transformers, because I will be adding transformers like ErrorT and WriterT.</p>
  
  <p><em>Question:</em> How to put Mutable Vector into State Monad using Monad Transformers ?</p>
  
  <p>I came up with following code that does not compile:</p>
  
  <pre><code>import Data.Vector
  import Control.Monad.State
  import Control.Monad.Identity
  import qualified Data.Vector.Mutable as VM
  import Control.Monad.ST
  import Control.Monad.ST.Trans
  type MyMon2 s a = StateT (VM.MVector s Int) (STT s Identity) a
  
  data Tree a = Null | Node (Tree a) a (Tree a) deriving Show
  main :: IO ()
  main = do 
      print $ runTraverse (Node Null 5 Null)
  
  runTraverse :: Tree Int -&gt; ((),Vector Int)
  runTraverse t = runIdentity (Control.Monad.ST.Trans.runST $ do
          emp &lt;- VM.replicate 7 0
          (_,x) &lt;- (runStateT (traverse t) emp)
          v &lt;- Data.Vector.freeze x
          return ((), v)
      )
  traverse :: Tree Int -&gt; MyMon2 s ()
  traverse Null = return ()
  traverse (Node l v r) = do
      d &lt;- get
      a &lt;- (VM.read d v)
      VM.write d v (a + 1)
      put d
      return ()
  </code></pre>
  
  <p>Compile errors are:</p>
  
  <pre><code>TranformersExample: line 16, column 16:
    Couldn't match type `s'
                    with `primitive-0.5.2.1:Control.Monad.Primitive.PrimState
                            (STT s Identity)'
        `s' is a rigid type variable bound by
            a type expected by the context: STT s Identity ((), Vector Int)
            at test/ExecutingTest.hs:15:30
      Expected type: STT s Identity (MVector s Int)
        Actual type: STT
                       s
                       Identity
                       (MVector
                          (primitive-0.5.2.1:Control.Monad.Primitive.PrimState
                             (STT s Identity))
                          Int)
      In the return type of a call of `VM.new'
      In a stmt of a 'do' block: emp &lt;- VM.new 7
      In the second argument of `($)', namely
        `do { emp &lt;- VM.new 7;
              (_, x) &lt;- (runStateT (traverse t) emp);
              v &lt;- freeze x;
              return ((), v) }'
  TranformersExample: line 26, column 14:
    Couldn't match type `s'
                    with `primitive-0.5.2.1:Control.Monad.Primitive.PrimState
                            (StateT (MVector s Int) (STT s Identity))'
        `s' is a rigid type variable bound by
            the type signature for traverse :: Tree Int -&gt; MyMon2 s ()
            at test/ExecutingTest.hs:21:13
      Expected type: MVector
                       (primitive-0.5.2.1:Control.Monad.Primitive.PrimState
                          (StateT (MVector s Int) (STT s Identity)))
                       Int
        Actual type: MVector s Int
      In the first argument of `VM.write', namely `d'
      In a stmt of a 'do' block: VM.write d v (a + 1)
      In the expression:
        do { d &lt;- get;
             a &lt;- (VM.read d v);
             VM.write d v (a + 1);
             put d;
             .... }
  </code></pre>
  
  <p><em>Note:</em> I am aware of not checking bounds.</p>