Haskell-在序列的下一个函数调用中使用先前计算的值

Question

我正在尝试为语法树算术运算创建一个函数，到目前为止，我几乎可以实现它了。在我附带的代码中，您可以看到我当前的函数定义。 eval是决定每次操作要做什么的功能，foldAndPropagateConstants是主要功能。 parse是一个简单的解析器，它采用数学表达式的String并返回等效树。例如

ghci> parse "3+x"
BinaryOperation Plus (Leaf (Constant 3)) (Leaf (Variable "x"))

我面临的问题是如何在后续操作中使用评估值。例如，此操作应如下工作：

ghci> foldAndPropagateConstants [("x", parse "1+2+3"), ("y", parse "5*x + 7")]
[("x",Leaf (Constant 6)),("y",Leaf (Constant 37))]

[请注意，在计算"x"的值时，函数应使用"y"的值。问题是，我似乎找不到在"x"函数中使用eval值的方法。

--foldAndPropagateConstants :: [(String, Exprv)] -> [(String, ExprV)]

eval :: ExprV -> Int
eval (Leaf (Variable n)) = --this part is what's missing
eval (Leaf (Constant n)) = n
eval (BinaryOperation Plus expr1 expr2) = eval expr1 + eval expr2
eval (BinaryOperation Times expr1 expr2) = eval expr1 * eval expr2
eval (UnaryOperation Minus expr1) = -1 * eval expr1

foldAndPropagateConstants (x:xs) = [(fst x, parse (show (eval(snd x)))) ] : foldAndPropagateConstants xs
foldAndPropagateConstants _ = []

Answer 1

编辑：我似乎只回答了问题的这一部分：

我似乎找不到在我的eval函数中使用“ x”值的方法。

由于您的问题不包含Minimal, Reproducible Example，因此这是您似乎在做的简化版本（不包含变量），该版本都包含data定义和eval函数：

module Eval where

data Expr
  = Constant Int
  | UnOp UnaryOperation Expr
  | BinOp BinaryOperation Expr Expr
  deriving (Eq, Show)

data UnaryOperation
  = UnaryMinus
  | UnaryFactorial
  | UnaryAbsolute
  deriving (Eq, Show)

data BinaryOperation
  = Plus
  | Minus
  | Times
  | Divide
  deriving (Eq, Show)

eval :: Expr -> Int
eval (Constant n) = n
eval (UnOp UnaryMinus e) = negate (eval e)
eval (UnOp UnaryFactorial e) = product [1..eval e]
eval (UnOp UnaryAbsolute e) = abs (eval e)
eval (BinOp bop e1 e2) = evalBinOp bop (eval e1) (eval e2)

evalBinOp :: BinaryOperation -> Int -> Int -> Int
evalBinOp Plus = (+)
evalBinOp Minus = (-)
evalBinOp Times = (*)
evalBinOp Divide = div

根据luqui的建议，在data Expr中用另一个构造函数扩展此求值器，并用“环境”扩展eval函数，在这种情况下，这是一个名称-值对列表：

data Expr
  = Constant Int
  | Variable String
  | UnOp UnaryOperation Expr
  | BinOp BinaryOperation Expr Expr
  deriving (Eq, Show)

-- ...

eval :: Expr -> [(String, Int)] -> Int
eval (Constant n) _env = n
eval (Variable s) env = lookup' s env
eval (UnOp UnaryMinus e) env = negate (eval e env)
eval (UnOp UnaryFactorial e) env = product [1..eval e env]
eval (UnOp UnaryAbsolute e) env = abs (eval e env)
eval (BinOp bop e1 e2) env = evalBinOp bop (eval e1 env) (eval e2 env)

-- ...

lookup' :: String -> [(String, Int)] -> Int
lookup' s [] = error ("Could not find variable " ++ s)
lookup' s ((t,n):env)
  | s == t = n
  | otherwise = lookup' s env

在我看来，此评估器最紧迫的改进是使用支持错误的返回类型更好地处理错误。我制作了lookup'辅助函数，因为标准库函数Data.List.lookup使用更安全的Data.List.lookup返回类型，这会鼓励我建议的重写：

Maybe

我在每个函数体中使用了不同的样式，但是它们都是相似主题的变体：case-of使用显式模式匹配，这很繁琐。 （想像一下使用case-of做

eval :: Expr -> [(String, Int)] -> Maybe Int
eval (Constant n) _env = pure n
eval (Variable s) env = lookup s env
eval (UnOp UnaryMinus e) env =
  case eval e env of
    Just n -> pure (negate n)
    Nothing -> Nothing
eval (UnOp UnaryFactorial e) env =
  eval e env >>= \n ->
  pure (product [1..n])
eval (UnOp UnaryAbsolute e) env =
  abs <$> eval e env
eval (BinOp bop e1 e2) env = do
  n1 <- eval e1 env
  n2 <- eval e2 env
  pure (evalBinOp bop n1 n2)

主体。）eval (BinOp ...)运算符的显式使用是...我想有些人喜欢它，但是>>=表示法看起来更漂亮。我认为，在这种情况下，do <$>是它们中最干净的。

接下来您可以做的是通过使用applicative style monad隐含env：有点混乱，Reader中只有一个函数体实际使用它，而其他所有函数体都将其丢弃或传递一起]。

Answer 2

您想要的是什么