如何在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

一个简单的Statemonad定义为:

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

这给你的是状态值的非确定性,只有在计算中的任何一点都可以观察到个别选择.

这里做的事情不是让是分支之间的任何互动; 在一个分支中进行的状态更改将永远不会从其他分支中看到,这是非确定性计算中通常所需的.