通过 List Monad 模拟非确定性选择

Question

我正在尝试为我正在使用的一种语言编写评估函数，在这种语言中，可以在称为选择块的 if 块中允许非确定性。我想要实现的是能够从 guard 为 true 的块中选择一个 if/selection 语句并对其进行评估，但我选择哪个并不重要。

通过搜索，我发现了一个 example，它的执行方式与我希望通过模拟投币翻转实现的方式类似。以下是我对它的改编，但我在将此逻辑应用于我的问题时遇到问题。

import Control.Monad

data BranchType = Valid | Invalid deriving (Show)
data Branch = If (Bool, Integer) deriving (Show, Eq)

f Valid   = [If (True, 1)]
f Invalid = [If (False, 0)]

pick = [Invalid, Invalid, Valid, Invalid, Valid]

experiment = do
        b <- pick
        r <- f b
        guard $ fstB r
        return r

s = take 1 experiment

fstB :: Branch -> Bool
fstB (If (cond, int)) = cond

main :: IO ()
main = putStrLn $ show $ s -- shows first branch which could be taken.

以下是我的 ADT 以及我一直在努力工作的内容：

data HStatement
  = Eval    HVal
  | Print   HVal
  | Skip    String
  | Do      HVal [HStatement]
  | If      (HVal, [HStatement])
  | IfBlock [HStatement] -- made up of many If
  | Select  [HStatement] -- made up of many If
  deriving (Eq, Read)


fstIf :: HStatement -> Bool
fstIf (If (cond, body)) = if hval2bool cond == True
                              then True
                              else False

h :: Env -> HStatement -> IOThrowsError ()
h env sb = do
         x <- g env sb
         guard $ fstIf x -- Couldn't match expected type ‘HStatement’ with actual type ‘[HStatement]’
         -- after guard, take 1 x then evaluate 

         

g :: Env -> HStatement -> IOThrowsError [HStatement]
g env (Select sb) = mapM (\x -> f env x) sb

f :: Env -> HStatement -> IOThrowsError HStatement
f env (If (cond, body)) = evalHVal env cond >>= \x -> case x of
                                                         Bool True  -> return $ If (Bool True,  body)
                                                         Bool False -> return $ If (Bool False, body)

我收到的错误如下：Couldn't match expected type ‘HStatement’ with actual type ‘[HStatement]’ 在 guard 行。我相信第一部分代码成功的原因是因为值是从 List 中提取的，但在第二种情况下，虽然它们是从列表中提取的，但它们是从 [HStatement], 而不是仅表示列表的东西...如果这有任何意义，我觉得我缺少词汇。

本质上，给定一个 n 语句的选择块，然后生成其中的一个子集，其守卫为真，并且只从中取出一个语句。

Answer 1

现在您已经记下了一些类型，错误消息已经很清楚了。 g returns IOThrowsError [HStatement]，所以当你将它的结果绑定到 h 中的 x 时，你就有了一个 [HStatement]。然后调用 fstIf，它需要一个 HStatement，而不是列表。您需要决定如何处理来自 g.

的多个结果

通过 List Monad 模拟非确定性选择

Simulating non-deterministic choice through the List Monad

haskell

monads

non-deterministic