从Monad状态上下文中展开值并连接两个状态上下文

我正在尝试为我的简单命令式语言解析器编写一个 eval 函数,但是当我使用 Control.MonadState 编写它时,我遇到了一些问题 .

evalComm s Let case 我需要打开类型( m Int )来传递 Int 更新功能,有没有办法做到这一点?

同样在 evalComm s Seq case ,我需要连接两个evalComm函数,以便以两种方式打开递归 . 是 liftM 这种情况的另一种选择?

type Env = [(Variable,Int)]

initState :: Env
initState = []

newtype State a = State { runState :: Env -> (a, Env) }

instance Monad State where
    return x = State (\s -> (x, s))
    m >>= f = State (\s -> let (v, s') = runState m s in
                           runState (f v) s')

instance Functor State where
    fmap = liftM

instance Applicative State where
    pure   = return
    (<*>)  = ap      

class Monad m => MonadState m where
    lookfor :: Variable -> m Int
    update :: Variable -> Int -> m ()

instance MonadState State where
    lookfor v = State (\s -> (lookfor' v s, s))
                where lookfor' v ((u, j):ss) | v == u = j
                                             | v /= u = lookfor' v ss
    update v i = State (\s -> ((), update' v i s))
                 where update' v i [] = [(v, i)]
                       update' v i ((u, _):ss) | v == u = (v, i):ss
                       update' v i ((u, j):ss) | v /= u = (u, j):(update' v i ss)

eval :: Comm -> Env
eval p = snd (runState (evalComm p) initState)

evalComm :: MonadState m => Comm -> m ()
evalComm c = case c of
                  Skip          -> return ()
                  Let v i       -> update v (evalIntExp i)
                  Seq c1 c2     -> return (liftM2 (:) (evalComm c2) (evalComm c1))

evalIntExp :: MonadState m => IntExp -> m Int
evalIntExp v = case v of
                    Const x             -> return (fromInteger x)
                    Var x               -> lookfor x
                    UMinus x            -> liftM (*(-1)) (evalIntExp x)
                    Plus x y            -> liftM2 (+) (evalIntExp x) (evalIntExp y)
                    Minus x y           -> liftM2 (-) (evalIntExp x) (evalIntExp y)
                    Times x y           -> liftM2 (*) (evalIntExp x) (evalIntExp y)
                    Div x y             -> liftM2 div (evalIntExp x) (evalIntExp y)


evalBoolExp :: MonadState m => BoolExp -> m Bool
evalBoolExp b = case b of
                     BTrue        -> return True
                     BFalse       -> return False
                     Eq x y       -> liftM2 (==) (evalIntExp x) (evalIntExp y)
                     Lt x y       -> liftM2 (<) (evalIntExp x) (evalIntExp y)
                     Gt x y       -> liftM2 (>) (evalIntExp x) (evalIntExp y)
                     And b0 b1    -> liftM2 (&&) (evalBoolExp b0) (evalBoolExp b1)
                     Or b0 b1     -> liftM2 (||) (evalBoolExp b0) (evalBoolExp b1)
                     Not b        -> liftM not (evalBoolExp b)

请注意,evalComm的代码不起作用,可能不正确 .

这是我的抽象语法树:

type Variable = String

data IntExp = Const Integer
            | Var Variable
            | UMinus IntExp
            | Plus IntExp IntExp
            | Minus IntExp IntExp
            | Times IntExp IntExp
            | Div IntExp IntExp
            | Quest BoolExp IntExp IntExp
 deriving Show

data BoolExp = BTrue
             | BFalse
             | Eq IntExp IntExp
             | Lt IntExp IntExp
             | Gt IntExp IntExp
             | And BoolExp BoolExp
             | Or BoolExp BoolExp
             | Not BoolExp
 deriving Show

data Comm = Skip
          | Let Variable IntExp
          | Seq Comm Comm
          | Cond BoolExp Comm Comm
          | While BoolExp Comm
          | Repeat Comm BoolExp
 deriving Show

回答(2)

2 years ago

让案例

正如Zigmond和Wagner所说, (>>=) 是适合这项工作的合适工具 . 我们来看看类型:

(>>=) :: m a -> (a -> m b) -> m b
update :: Variable -> Int -> m ()
evalIntExp i :: m Int
v :: Variable

你能想出一种方法将这些组合成预期的类型 m () 吗?请记住,您可以部分应用函数来获取一个参数较少的函数 .

Seq案例

让我们再看一下这些类型 .

我们有两个类型为 m () ,( evalComm c1evalComm c2 )的值,并希望将它们组合成 m () 类型的值 . 我们可以通过创建一个忽略其参数的函数来再次使用 >>=

Seq c1 c2  -> (evalComm c1) >>= (\x -> (evalComm c1))

但是,这是一个常见的场景,因此已有一个内置函数:

(>>) :: m a -> m b -> m b

Seq c1 c2  -> evalComm c1 >> evalComm c1

我们来看看你以前的代码吧

liftM2 (:) :: m a -> m [a] -> m [a]

您没有列表,所以这没用 .

liftM2 :: (a -> b -> c) -> m a -> m b -> m c

如果 a = b = c = () 可以使用它,但与仅使用 >> 相比,这是不必要的复杂 . 但是,我鼓励你尝试将它作为练习 . () -> () -> () 类型的函数如何显示?

return :: a -> m a

当你有一个纯值并需要将它转换为monadic值时使用它,所以不需要在这里使用它 . 结果将是双包装类型 m (m ()) ,这不是你想要的 .

最后的话

如您所见,在编写Haskell程序时,这些类型非常有用 . 每当你想知道什么可以组合时,看看类型 . 您可以在GHCi中键入 :t <expression> 来查看表达式的类型 .

2 years ago

两件事情 .

首先,我认为你的更新功能是错误的,因为你的模式匹配相同的东西两次 . 为什么不?:

update v i = State (\s -> ((), update' v i s))
             where update' v i [] = [(v, i)]
                   update' v i ((u, j):ss) | v == u = (v, i):ss
                                           | v /= u = (u, j):(update' v i ss)

此更新功能正在创建对列表 . 正如@Hjulle发布的那样,使用 >> 运算符将执行:计算第一个结果,然后计算第二个结果 . 在这种情况下,使用 evalComm 计算结果最终会更新状态或返回 () . 所以你的代码应该是这样的:

evalComm :: MonadState m => Comm -> m ()
evalComm c = case c of
                  Skip          -> return ()
                  Let v i       -> evalIntExp i >>= \o -> update v o
                  Seq c1 c2     -> evalComm c1 >> evalComm c2

evalIntExp i >>= \o -> update v o 表示:计算 evalIntExp i ,将得到的 Int a传递给 update 函数

此实现返回:

let exp1 = Seq (Seq (Let "string1" (Const 1)) (Let "string2" (Const 2))) Skip 

> eval exp1
[("string1",1),("string2",2)]

但在其他例子中失败了 .