haskell - 如何在 Haskell 中构建非确定性状态 monad？

Question

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

谢谢。

Answer 1

一个简单的 State monad 定义为:

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

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

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