如何把可变的向量放入状态Monad [英] How to put mutable Vector into State Monad

问题描述

 导入数据在haskell中编写小程序来计算树中Int值的所有出错次数.Vector 
导入Control.Monad.State 
导入Control.Monad.Identity 
 
数据树a =空|节点（树a）a（树a）派生Show 
 main :: IO（）
 main = do 
 print $ runTraverse（节点空5空）
 
 
类型MyMon a = StateT（Vector Int）标识a 
 
 runTraverse :: Tree Int  - > （（），Vector Int）
 runTraverse t = runIdentity（runStateT（traverse t）（Data.Vector.replicate 7 0））
 
遍历:: Tree Int  - > MyMon（）
遍历Null = return（）
遍历（Node lvr）= do 
s<  -  get 
 put（s // [（v，（s！v） + 1）]） -  s [v]：= s [v] + 1 
遍历l 
遍历r 
 return（）
  

但是不可变向量的'更新'是以O（n）复杂度完成的。
我正在寻找O（1）的更新和O（1）的访问。
据我所知可变载体做我想要的。要使用它们，我需要使用ST或IO。
因为我想要做一些UnitTests，我更喜欢ST monad，但我不想在函数调用中传递该向量。
我需要继续使用Monad变形金刚，因为我将添加像ErrorT和WriterT这样的变形金刚。

问题：如何使用Monad变换器将可变矢量转换为状态Monad？

我想出了以下不能编译的代码：

  import Data.Vector 
导入Control.Monad.State 
导入Control.Monad.Identity 
将限定的Data.Vector.Mutable导入为VM 
 import Control.Monad.ST 
 import Control.Monad.ST.Trans 
 type MyMon2 sa = StateT（VM.MVector s Int）（STT s Identity）a 
 
数据树a = Null |节点（树a）a（树a）派生Show 
 main :: IO（）
 main = do 
 print $ runTraverse（节点空5空）
 
 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）
）
遍历:: Tree Int  - > ; MyMon2 s（）
遍历Null = return（）
遍历（Node lvr）= do 
d<  -  get 
a < - （VM.read dv）
 VM.write dv（a + 1）
 put d 
 return（）
  

编译错误是：

  TranformersExample：第16行，第16列：
无法匹配类型's'
与`primitive-0.5.2.1：Control.Monad.Primitive.PrimState 
（STT s Identity）'
`s'是一个刚性类型变量，由
a类型上下文：STT s Identity（（），Vector Int）
 at test / ExecutingTest.hs：15：30 
预期类型：STT s标识（MVector s Int）
实际类型：STT 
s 
 Identity 
（MVector 
（primitive-0.5.2.1：Control.Monad.Primitive.PrimState 
（STT s Identity））
 Int ）
在`VM.new'调用的返回类型中
在'do'块的语句中：emp < -  VM.new 7 
在` （$）'，即
`do {emp < -  VM.new 7; 
（_，x）<  - （runStateT（traverse t）emp）; 
 v < -  freeze x; 
 return（（），v）}'
 TranformersExample：第26行，第14列：
无法将类型's'
与`primitive-0.5.2.1：Control .Monad.Primitive.PrimState 
（StateT（MVector s Int）（STT s Identity））'
`s'是一个刚性类型变量，由
绑定，用于遍历:: Tree Int  - > MyMon2 s（）
 at test / ExecutingTest.hs：21：13 
预期类型：MVector 
（primitive-0.5.2.1：Control.Monad.Primitive.PrimState 
（StateT （MVector s Int）（STT s Identity）））
 Int 
实际类型：MVector s Int 
在'VM.write'的第一个参数中，即'd'
在'do'块的标记中：VM.write dv（a + 1）
在表达式中：
 do {d < -  get; 
 a<  - （VM.read d v）; 
 VM.write d v（a + 1）; 
放d; 
 ....} 
  

注意：我知道没有检查边界。

解决方案

当使用 ST 永远不会明确地传递向量（它总是隐藏在 s 参数中），而是引用它。这个引用是不可变的，不会被复制，所以你不需要 State ，只是一个读者隐式地传递它。

 导入Data.Vector 
导入Control.Monad.Reader 
将合格的Data.Vector.Mutable导入为VM 
导入Control.Monad.ST 
 
 type MyMon3 s = ReaderT（VM.MVector s Int）（ST s）
 
数据树a =空|节点（树a）a（树a）派生Show 
 main :: IO（）
 main = do 
 print $ runTraverse（节点空5空）
 
 runTraverse :: Tree Int  - > Vector Int 
 runTraverse t = runST $ do 
 emp<  -  VM.replicate 7 0 
 runReaderT（遍历t）emp 
 Data.Vector.freeze emp 
 
 traverse :: Tree Int  - > MyMon3 s（）
遍历Null = return（）
遍历（Node lvr）= do 
d<  -  ask 
a<  -  lift $ VM.read dv 
 lift $ VM.write dv（a + 1）
  

I wrote small program in haskell to count all ocurences of Int values in Tree using State Monad with 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 ()

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.

Question: How to put Mutable Vector into State Monad using Monad Transformers ?

I came up with following code that does not compile:

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

Compile errors are:

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

Note: I am aware of not checking bounds.

解决方案

When using ST state you're never explicitly passing the vector around (that's always in hidden in the s argument), but a reference to it. That reference is immutable and not copied, so you need not State but simply a reader to pass it implicitly.

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)

这篇关于如何把可变的向量放入状态Monad的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！