4

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

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]但最终，一旦我将 list monad 的分支包装在状态包装器中，我就无法删除它，对吧？那么有没有办法做到这一点？

谢谢。

4

1 回答 1

14

一个简单的Statemonad 定义为：

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

这代表了一个自包含和确定性的有状态计算。考虑[]作为一个非确定性的单子，你可以有[State s a]它代表一组非确定性的确定性计算，或者State s [a]它代表一个确定性计算产生一组非确定性的值。在这两种情况下，有状态计算本身的结构中都不存在任何不确定性。

要以您想要的方式实际结合状态和非确定性行为，您需要以一种无法使用 just 的方式将两者结合起来State；这就是monad转换器的目的。类型StateT s [] a等价于：

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

这给您的是状态值的不确定性，在计算中的任何一点都只能观察到个人选择。

这不允许分支之间的任何交互；在一个分支中所做的状态更改将永远不会从其他分支中看到，这是非确定性计算中通常需要的。

于 2012-12-12T16:37:15.677 回答