haskell - 如何评估由 ADT 构建的表达式

Question

这是我的 ADT：

data Ex a = I Integer  --integer
           | Add (Ex a) (Ex a) --add 
           | Variable a --variable
           | Def [(a, Ex a)] (Ex a) --defining local variables

这是我的评估功能：

eval :: Ex a -> Integer
eval (I n) = n
eval (Add e1 e2) = eval e1 + eval e2

我如何继续eval和？VariableDef

Answer 1

更多提示可帮助您自己编写解决方案。

一些建议

• 您需要lookup在类型列表上执行[(a,Ex a)]，因此需要Eq a对此进行限制。
• 如果您没有定义局部变量并使用它，您的评估可能会失败。在这种情况下，eval函数应该返回Nothingelse Just answer。
• 我已经写了你的大部分代码，你唯一需要写的地方就是Variable a案例。这非常简单，因为如果成功 else ，您只需要lookup输入并在评估后返回值。xslookupNothing

代码变成

eval :: Eq a => Ex a -> Maybe Integer
eval = eval' []
  where eval' :: Eq a => [(a, Ex a)] -> Ex a -> Maybe Integer
        eval' _ (I n) = Just n
        eval' xs (Add e1 e2) = liftA2 (+) (eval' xs e1) (eval' xs e2) -- liftA2 from Control.Applicative
        eval' xs (Variable a) = -- write your code here
        eval' xs (Def ys e) = eval' (ys ++ xs) e -- Think of the order in which you want to combine two binding if same named variable is present in both xs and ys.

Answer 2

这里有一个提示：

eval :: Ex a -> Integer
eval = eval' []
  where eval' :: [(a, Integer)] -> Ex a -> Integer
        eval' _ (I n) = n
        -- etc