我正试图为我的简单命令式语言解析器编写一个eval
函数,但当我使用Control.Monad和State编写它时,我遇到了一些问题。
在evalComm
sLet case时,我需要打开类型(m Int(来传递Intto update函数,有办法吗?
同样在evalComm
sSeq情况下,当递归以两种方式打开时,我需要连接两个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
Let案例
正如Zigmond和Wagner所说,(>>=)
是适合这份工作的工具。让我们看看类型:
(>>=) :: m a -> (a -> m b) -> m b
update :: Variable -> Int -> m ()
evalIntExp i :: m Int
v :: Variable
你能想出一种方法把它们组合成预期的类型m ()
吗?请记住,您可以部分应用一个函数来返回一个参数较少的函数。
Seq案例
让我们再看一下类型。
我们有两个类型为m ()
的值(evalComm c1
和evalComm 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
当您有一个纯值并且需要将其转换为一元值时,就可以使用它,所以不需要在这里使用它。结果将是双包装类型m (m ())
,这不是您想要的。
词尾词
正如您所看到的,在编写Haskell程序时,类型可能非常有用。每当你想知道哪些东西可以组合在一起时,看看它们的类型。您可以通过在GHCi中键入:t <expression>
来检查表达式的类型。
两件事。
首先,我认为你的更新功能是错误的,因为你对同一件事进行了两次模式匹配。为什么不呢?:
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
并将其传递给update
函数
此实现返回:
let exp1 = Seq (Seq (Let "string1" (Const 1)) (Let "string2" (Const 2))) Skip
> eval exp1
[("string1",1),("string2",2)]
但在其他例子中失败了。