Come mettere Vector mutevole in Stato Monade

Question

ho scritto piccolo programma in Haskell per contare tutti i ocurences di valori INT in Tree usando Stato Monad con Vector:

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 -> ((),Vector Int) 
runTraverse t = runIdentity (runStateT (traverse t) (Data.Vector.replicate 7 0)) 

traverse :: Tree Int -> MyMon() 
traverse Null = return() 
traverse (Node l v r) = do 
    s <- get 
    put (s // [(v, (s ! v) + 1)]) -- s[v] := s[v] + 1 
    traverse l 
    traverse r 
    return() 

Ma 'update' di Vettori immutabili è fatto in O (n) complessità. E sto cercando l'aggiornamento in O (1) e l'accesso in O (1). Come ho capito, i Vettori Mutevoli fanno quello che voglio. Per usarli ho bisogno di usare ST o IO. Perché mi piacerebbe fare alcuni test unitari, preferisco la monade ST, ma non voglio dover passare quel vettore in giro per le chiamate di funzione. Ho bisogno di continuare ad usare Monad Transformers, perché aggiungerò trasformatori come ErrorT e WriterT.

Domanda: Come mettere il vettore mobile in Monade stato utilizzando Monade Transformers?

mi si avvicinò con seguente codice che non può essere compilato:

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 -> ((),Vector Int) 
runTraverse t = runIdentity (Control.Monad.ST.Trans.runST $ do 
     emp <- VM.replicate 7 0 
     (_,x) <- (runStateT (traverse t) emp) 
     v <- Data.Vector.freeze x 
     return ((), v) 
    ) 
traverse :: Tree Int -> MyMon2 s() 
traverse Null = return() 
traverse (Node l v r) = do 
    d <- get 
    a <- (VM.read d v) 
    VM.write d v (a + 1) 
    put d 
    return() 

Errori di compilazione sono:

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 <- VM.new 7 
    In the second argument of `($)', namely 
     `do { emp <- VM.new 7; 
      (_, x) <- (runStateT (traverse t) emp); 
      v <- 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 -> 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 <- get; 
      a <- (VM.read d v); 
      VM.write d v (a + 1); 
      put d; 
      .... } 

Nota: Sono consapevole di non controllare limiti.

Answer 1

Quando si utilizza ST Stato si è mai passando esplicitamente il vettore intorno (che è sempre nascosta nell'argomento s), ma un riferimento ad esso. Quel riferimento è immutabile e non copiato, quindi non è necessario State ma semplicemente un lettore per passarlo implicitamente.

import Data.Vector 
import Control.Monad.Reader 
import qualified Data.Vector.Mutable as VM 
import Control.Monad.ST 

type MyMon3 s = ReaderT (VM.MVector s Int) (ST s) 

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 -> Vector Int 
runTraverse t = runST $ do 
     emp <- VM.replicate 7 0 
     runReaderT (traverse t) emp 
     Data.Vector.freeze emp 

traverse :: Tree Int -> MyMon3 s() 
traverse Null = return() 
traverse (Node l v r) = do 
    d <- ask 
    a <- lift $ VM.read d v 
    lift $ VM.write d v (a + 1)