如何在Haskell中构建一个不确定的状态monad？

我想在Haskell中构建一个不确定状态monad。这将允许我使用内置状态生成搜索空间中的所有元素以修剪不良位置。假设我有以下的（伪）代码：如何在Haskell中构建一个不确定的状态monad？

primitives :: [State Int Element] 
primitives = [... list of primitive stateful elements ...]                              
combine :: Element -> Element -> State Int Element                            
expand :: Depth -> [State Int Element]                               
expand 0 = primitives                                   
expand d = do                                     
    ... do something to the state ...                               
    left <- expand (d-1)                                   
    right <- expand (d-1)                                  
    let out = combine left right                                 
    guard (... some check on out ...)                               
    return out

这里有几件事情，不工作：我需要了解最基本的是如何做一些状态，然后管它到expand分支中的每一个。我尝试了一堆类型为State Int [ State Int Element]的函数，但是最终一旦我在状态包装中包装了列表monad的分支，我无法删除它，对吧？那么有没有办法做到这一点？

谢谢。

来源

2012-12-12 Eyal

StateT monad允许您跟踪状态，同时也利用另一个monad，如IO或Rand（用于随机值）。如果我已经正确理解你的问题，我认为StateT将解决你的问题。你能举一个你想在'primitives'数组中有什么样的东西的例子吗？ – mhwombat

听起来像LogicT monad变换器：http://hackage.haskell.org/package/logict与您的非确定性状态monad是'LogicT（状态Int）元素'。公平的连词，条件和修剪作为奖励。比简单列表更有效的实现。 –

一般注意事项：不要建立自己的组合单体，使用单体变压器。 – permeakra

简单State单子被定义为：

data State s a = State (s -> (a, s))

这代表了自包含的，确定性的状态计算。考虑将[]作为非确定性monad，可以有[State s a]表示确定性计算的非确定性集合，或者State s [a]表示确定性计算，产生非确定性值集合。在任何情况下，在有状态计算本身的结构中都不存在任何非确定性。

要实际上结合状态和非确定性行为，你似乎想要的方式，你需要结合这两种方式是不可能使用只是State;这是monad变压器的目的。该类型StateT s [] a相当于：

data NonDetState s a = NonDetState (s -> [(a, s)])

这是什么给你是不确定性与在计算任何一个点观察到的只是个人选择的状态值。

这是什么不是允许是分支之间的任何交互;在一个分支中进行的状态变化将永远不会从其他分支中看到，这是非确定性计算中通常需要的。

来源

2012-12-12 16:37:15

如何在Haskell中构建一个不确定的状态monad？

回答

相关问题