标签: state-monad

我需要编写一个也可以支持错误处理的状态monad.我正在考虑将Either monad用于此目的,因为它还可以提供有关导致错误的原因的详细信息.我发现使用也许单子的状态单子的定义,但我无法修改为使用,而不是可能.这是代码:

newtype StateMonad a = StateMonad (State -> Maybe (a, State))

instance Monad StateMonad where
(StateMonad p) >>= k = StateMonad (\s0 -> case p s0 of 
                                 Just (val, s1) -> let (StateMonad q) = k val in q s1
                                 Nothing -> Nothing)
return a = StateMonad (\s -> Just (a,s))

data State = State
{ log  :: String
, a    :: Int}

我想使用节点和唯一键的IntMap创建图形结构.这里和这里已经很好地介绍了这个主题.我理解状态monad是如何工作的,基本上将状态函数 - >(val,state)包装在newtype中,这样我们就可以为它创建一个monad实例.我已经阅读了很多相关主题.我仍然无法理解如何在程序执行过程中获得唯一(或仅增量)值.获得一系列连续的ID很容易,但是一旦我"runState"退出monad,似乎我回到了我开始跟踪当前ID的位置.我觉得我被卡在了monad中.我考虑的另一个选择是保持整个IntMap和当前"下一个"ID作为状态,但这似乎非常"必要"和极端.这个问题非常相似,但没有得到很多答案(或者我可能只是错过了一些明显的答案).在程序执行过程中利用状态monad获取唯一ID的惯用方法是什么？谢谢.

我希望我的术语在这里是正确的 - 如果没有,随时编辑任何东西.

我正在使用Haskell作为辅助语言,同时撰写关于组合博弈论的论文 - 也就是说,我的所有函数都只是兼顾数字并帮助我找到我正在研究的游戏的解决方案.

我为具体的,整体的"板尺寸"编写了所有功能(想想chequerboard,5x5等).我想扩展到任何规模的研究板,因此通过包含Integer参数来修改所有相关功能.例如,

type Size = Int

squares :: Size -> [Square]
squares size = [ (x,y) | x <- [1..size],  
                         y <- [1..size]]

然而,这开始变得混乱.通常我认为与大小无关的函数在访问需要大小的函数时必须提供大小.

这很快导致这样的行:

reaching size = (losing size) \\\ (setA size)

takeUDmir _  []       = []
takeUDmir size (x:xs) = [x] ++ takeUDmir size (xs \\\ mirUD size x)

rotate size s = concatMap (mirUD size) (mirLR size s)

(请注意,函数的内容确实无关紧要,我只是想表明它已经变得无用了.)

我非常有信心使用Haskell,并且通常使用函数式编程,但我不知道如何去除所有这些size引用,并且仅仅依赖于为需要使用它的每个函数设置大小的其他东西. .

我想我可能正在寻找一个单子,但我不知道.

我在haskell中编写了一个小程序,使用State Monad with Vector计算Tree中所有的Int值的出现次数:

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 …

parsec包的文档声明该 u参数用于通过monadic计算来携带一些用户状态.但是通过ParsecT在Statemonad 上建立monad 变换器可以实现相同的功能.因此,如果我的解析器不是有状态的,我不需要u完全,但必须将其设置为()parsec.添加非可选状态支持的理由是什么ParsecT？

最近,我已经从Stackoverflow中的Graph中提出了构建DFS树的问题,并且已经了解到可以使用State Monad简单地实现它.

在haskell的DFS

虽然DFS要求仅跟踪被访问节点,因此我们可以使用"Set"或"List"或某种线性数据结构来跟踪被访问节点,BFS需要完成"被访问节点"和"队列"数据结构.

我的BFS伪代码是

Q = empty queue
T = empty Tree
mark all nodes except u as unvisited
while Q is nonempty do
u = deq(Q)
    for each vertex v ? Adj(u)
        if v is not visited 
        then add edge (u,v) to T
             Mark v as visited and enq(v)

从伪代码可以推断,我们每次迭代只需要做3个进程.

1. 从队列中出列点
2. 将点的所有未访问的邻居添加到当前树的子节点,队列和"已访问"列表
3. 在队列中重复此操作

由于我们没有使用递归遍历进行BFS搜索,我们需要一些其他的遍历方法,例如while循环.我在hackage中查找了loop-while包,但似乎有点弃用了.

我假设我需要这样的代码:

{-...-}
... =   evalState (bfs) ((Set.singleton start),[start])
where 
    neighbors x = Map.findWithDefault [] x adj 
    bfs =do (vis,x:queue)<-get
             map (\neighbor ->
                  if (Set.member …

我一直在努力了解State Monad.与其如何使用不同,尽管这并不总是很容易找到.但是我发现的State Monad的每一次讨论基本上都有相同的信息,总有一些我不理解的东西.

以这篇文章为例.其中作者有以下内容:

case class State[S, A](run: S => (A, S)) {
...
  def flatMap[B](f: A => State[S, B]): State[S, B] =
    State(s => {
      val (a, t) = run(s)
      f(a) run t
    })
...
}

我可以看到类型正确排列.但是,我根本不理解第二个run.

也许我正在错误地看待这个monad的整个目的.我从HaskellWiki得到的印象是,状态monad有点像run允许转换的状态机(但在这种情况下,状态机并不像大多数状态机那样具有固定的状态转换).如果是这种情况,那么在上面的代码(a, t)中将表示单个转换.应用程序f将表示该值的修改和State(生成新的State对象).这让我完全不知道第二个run是什么.这似乎是第二次"过渡".但这对我没有任何意义.

我可以看到,调用run生成的State对象会产生一(A, S)对新的对,当然,这些类型需要排列.但我真的不明白这应该是做什么的.

那么,这里到底发生了什么？在这里建模的概念是什么？

编辑:2015年12月22日

所以,看来我并没有很好地表达我的问题.让我试一试.

在同一篇博文中,我们看到以下代码map:

def map[B](f: A => B): State[S, B] =
  State(s => {
    val …

我一直在尝试围绕monad的概念,我一直在尝试以下示例:

我有一个Editor数据类型,表示文本文档的状态和一些工作的功能.

data Editor = Editor {
  lines :: [Line],    -- editor contents are kept line by line      
  lineCount :: Int,   -- holds length lines at all times
  caret :: Caret      -- the current caret position
  -- ... some more definitions
} deriving (Show)

-- get the line at the given position (first line is at 0)
lineAt :: Editor -> Int -> Line
lineAt ed n = ls !! n
  where
    ls = lines ed

-- get …

我完全混淆了

newtype StateT s m a = StateT {runStateT :: s -> m (a, s)}

和

type State s = StateT s Identity

和

class Monad m => MonadState s m | m -> s

我正在使用Scala Cats库中的State monad来以功能方式构成命令转换的命令式序列。

import cats.data.State
import scala.util.{Failure, Success, Try}

// State being maintained: an immutable counter.
final case class Counter(count: Int)

// Type for state transition operations.
type Transition[M] = State[Counter, Try[M]]

// Operation to increment a counter.
val increment: Transition[Unit] = State {c =>

  // If the count is at its maximum, incrementing it …