Làm thế nào để đưa Vector có thể thay đổi vào Nhà nước Monad

Question

tôi đã viết chương trình nhỏ trong Haskell để đếm tất cả ocurences các giá trị Int trong Tree sử dụng Nhà nước Monad với 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() 

Nhưng 'cập nhật' của Vectors bất biến được thực hiện trong thời gian O (n) phức tạp. Và tôi đang tìm bản cập nhật trong O (1) và truy cập trong O (1). Vì tôi hiểu Mutable Vectors làm những gì tôi muốn. Để sử dụng chúng tôi cần sử dụng ST hoặc IO. Bởi vì tôi muốn làm một số UnitTests tôi thích ST monad, nhưng tôi không muốn phải vượt qua vector đó xung quanh trong các cuộc gọi chức năng. Tôi cần tiếp tục sử dụng Monad Transformers, vì tôi sẽ thêm các máy biến áp như ErrorT và WriterT.

Câu hỏi: Làm thế nào để đặt Vector có thể biến đổi thành Monad trạng thái bằng Monad Transformers?

tôi đã đưa ra đoạn mã sau mà không biên dịch:

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

Biên dịch lỗi là:

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

Lưu ý: tôi biết không kiểm tra giới hạn.

Answer 1

Khi sử dụng ST, bạn đang không bao giờ chuyển rõ ràng vectơ xung quanh (luôn ẩn trong đối số s), nhưng là tham chiếu đến nó. Tham chiếu đó là bất biến và không được sao chép, vì vậy bạn không cần phải State mà chỉ đơn giản là một người đọc để vượt qua nó một cách ngầm định.

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)