通过 List Monad 模拟非确定性选择
Simulating non-deterministic choice through the List Monad
我正在尝试为我正在使用的一种语言编写评估函数,在这种语言中,可以在称为选择块的 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
语句的选择块,然后生成其中的一个子集,其守卫为真,并且只从中取出一个语句。
现在您已经记下了一些类型,错误消息已经很清楚了。 g
returns IOThrowsError [HStatement]
,所以当你将它的结果绑定到 h
中的 x
时,你就有了一个 [HStatement]
。然后调用 fstIf
,它需要一个 HStatement
,而不是列表。您需要决定如何处理来自 g
.
的多个结果
我正在尝试为我正在使用的一种语言编写评估函数,在这种语言中,可以在称为选择块的 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
语句的选择块,然后生成其中的一个子集,其守卫为真,并且只从中取出一个语句。
现在您已经记下了一些类型,错误消息已经很清楚了。 g
returns IOThrowsError [HStatement]
,所以当你将它的结果绑定到 h
中的 x
时,你就有了一个 [HStatement]
。然后调用 fstIf
,它需要一个 HStatement
,而不是列表。您需要决定如何处理来自 g
.