Wie wandelbar Vector in Staat Monad

Question

Ich schrieb kleines Programm in Haskell setzen alle ocurences von Int-Werten im Baum mit Staat Monad mit Vector zu zählen:

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() 

Aber ‚update‘ unveränderlicher Vektoren ist in O getan (n) Komplexität. Und ich suche nach Update in O (1) und Zugriff in O (1). Wie ich verstehe, machen Mutable Vectors was ich will. Um sie zu benutzen, muss ich ST oder IO benutzen. Da ich gerne UnitTests machen würde, bevorzuge ich ST monad, aber ich möchte diesen Vektor nicht in Funktionsaufrufen übergeben müssen. Ich muss weiterhin Monad Transformers verwenden, weil ich Transformatoren wie ErrorT und WriterT hinzufügen werde.

Frage: Wie setze ich Veränderlichen Vektor in State Monad mit Monad Transformers?

kam ich mit folgendem Code auf, der nicht kompilieren:

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() 

Kompilieren Fehler sind:

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; 
      .... } 

Hinweis: Ich bin mir bewusst, nicht überprüft Grenzen.

Answer 1

Wenn ST Zustand verwendet bist du nie um den Vektor ausdrücklich vorbei (das ist immer in der s Argument versteckt), sondern ein Hinweis auf sie. Diese Referenz ist unveränderlich und wird nicht kopiert, Sie brauchen also nicht einfach einen Reader, um sie implizit zu übergeben.

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)