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]が、最終的には、リストモナドのブランチを状態ラッパーでラップすると、削除できなくなります。それで、これを行う方法はありますか？

ありがとう。

4

1 に答える 1

14

単純なStateモナドは次のように定義されます。

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

これは、自己完結型で決定論的なステートフルな計算を表します。[]非決定論的モナドと見なすと、決定論的計算の非決定論的セットを表すか、非決定論的値のセットを生成する決定論的計算を表す which を持つことができ[State s a]ますState s [a]。どちらの場合も、ステートフルな計算自体の構造に非決定性は存在しません。

状態と非決定性の動作を希望どおりに実際に組み合わせるStateには、 ;だけでは不可能な方法で 2 つを組み合わせる必要があります。これがモナド変換子の目的です。タイプStateT s [] aは次と同等です。

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

これにより、状態値の非決定性が得られ、計算の任意の時点で個々の選択のみが観察されます。

これが許可しないのは、ブランチ間の相互作用です。1 つのブランチで行われた状態の変更は、他のブランチからは決して見えません。これは、非決定論的な計算で一般的に望まれることです。

于 2012-12-12T16:37:15.677 に答える