时间戳

首页 > 解决方案 > Haskell：将任何 Ast 评估为字符串

haskell - Haskell：将任何 Ast 评估为字符串

问题描述

我有一个分配，我必须编写一个评估函数 eval::Ast -> String ，它将任何 Ast 评估为一个字符串。例如：

>eval (parse "hel + lo") 
"hello"

> eval (parse "mi + 2 * la")
"milala"

我制作了一个解析函数，例如采用“hel + lo”并返回 Plus (Word "hel") (Word "lo")

但是我非常不确定函数（和类型）应该是什么样子，因为 AST 的评估涉及多种类型......谁能让我朝着正确的方向前进？

AST 定义为

data Ast 
 = Word String
 | Num Int
 | Mult Ast Ast
 | Plus Ast Ast
 | Minus Ast Ast
 deriving (Eq, Show)

标签： haskell

解决方案

eval :: AST -> String是什么定义了你的操作的语义。例如，eval (Plus (Word x) (Word y)) == x ++ y。

eval (Plus x y)但是，如果两个参数都是数字，应该产生什么？它应该连接它们，还是以数字方式添加它们？如果其中任何一个本身是 、 或 值之一Plus怎么Minus办Mul？您需要首先评估它们，但是您无法判断结果"2"是真的是字符串还是数字的结果。

您还需要确定是否AST 可以评估每个：Mul (Word "x") (Word "y")有意义吗？如果不是，你String会返回什么？

我建议两件事：

首先，定义一个simplify函数，负责将AST简化为更简单的东西。它会在 的 情况下处理诸如数值算术之类的Plus (Num ...) (Num ...)事情，但保持Word xor之类的事情Plus (Word x) (Num y)不变。

simplify :: AST -> AST
simplify (Num x) = Num x  -- Easy case done for you; no simplification necessary
simplify (Word x) = ...
-- Hint: in each of the following, you need to recursively simplify the operands.
-- Once you do that, you can either simplify further, or return a new
-- node to be evaluated.
simplify (Plus x y) = ...
simplify (Minus x y) = ...
simplify (Mul x y) = ...

其次， defineeval :: AST -> Either String String将首先simplify在其参数上使用，然后AST在可行的情况下将s逐个转换，Strings并在不可行的情况下返回适当的错误消息。

eval :: AST -> Either String String
eval x = eval' (simplify x)
   where eval' (Word x) = Right x  -- Easy case done for you
         eval' (Num x) = ...
         -- simplify will have reduced all the Num + Num, Num - Num, and
         -- Num * Num nodes to single Num nodes already.
         eval' (Plus (Word x) (Word y)) = x ++ y  -- Other easy case done above
         eval' (Plus x y) = ...
         eval' (Minus (Word x) (Word y)) = ...
         eval' (Minus x y) = ...
         eval' (Mul (Word x) (Word y)) = ...
         eval' (Mul x y) = ...

请注意，您可以想象在eval'or中定义一些组合simplify，例如

simplify (Plus (Word x) (Word y)) == Word $ x ++ y

将更复杂（并且可能不可能）的情况留给eval.

推荐阅读