Haskell

Question

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

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))]

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

--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

编辑：我好像只回答了这部分问题：

I can't seem to find a way to use "x" value in my eval function.

由于您的问题不包含 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

用 data Expr 中的另一个构造函数扩展此求值器，并如 luqui 所建议的那样用 "environment" 扩展 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

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

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)

我在每个函数体中使用了不同的风格，但它们都是相似主题的变体：case-of 使用显式模式匹配，这变得乏味。（想象一下使用 case-of 来处理 eval (BinOp ...) 主体。） >>= 运算符的显式使用是……我想有些人喜欢它，但是 do 符号看起来更漂亮。我认为 <$> applicative style 是本例中最简洁的。

接下来你可以做的是通过使用 Reader monad 使 env 隐式化：eval 中只有一个函数体实际使用它有点混乱，并且其他人要么扔掉要么传下去。

Answer 2

你想要的是为了

foldAndPropagateConstants [("x", parse "1+2+3"), ("y", parse "5*x + 7"), ("z", parse "x+y-1")]

相当于

 =  let s0 = []

        r1 = parse' "1+2+3" s0
        -- r1 = Leaf (Constant 6)
        s1 = [("x",6)]

        r2 = parse' "5*x + 7" s1 
        -- r2 = Leaf (Constant 37)
        s2 = [("x",6),("y",37)]

        r3 = parse' "x+y-1" s2 
        -- r3 = Leaf (Constant 42)
        s3 = [("x",6),("y",37),("z",42)]
    in
       [r1,r2,r3]

parse' 类似于 parse，但它还可以查询目前已知的值存储，并将其作为第二个参数接收。

如果重组为

，上面的代码更容易用函数编码

 =  let s0 = []

        (s1, r1) = parse'' "1+2+3" s0
        -- r1 = Leaf (Constant 6)
        -- s1 = [("x",6)]

        (s2, r2) = parse'' "5*x + 7" s1 
        -- r2 = Leaf (Constant 37)
        -- s2 = [("x",6),("y",37)]

        (s3, r3) = parse'' "x+y-1" s2 
        -- r3 = Leaf (Constant 42)
        -- s3 = [("x",6),("y",37),("z",42)]
    in
       snd (s3, [r1,r2,r3])

顺便说一句，这种 状态传递计算 的模式被称为状态单子，但这是另一天的事。

当表示为

时，以上符合递归模式

foldAndPropagateConstants [("x", parse "1+2+3"), ("y", parse "5*x + 7"), ("z", parse "x+y-1")] = 
    snd $ foldAndPropagateConstants' 
            [("x", parse "1+2+3"), ("y", parse "5*x + 7"), ("z", parse "x+y-1")] 
            []

foldAndPropagateConstants' [("x", parse "1+2+3"), ("y", parse "5*x + 7"), ("z", parse "x+y-1")] s0 =
    let 
        (s1, r1) = parse'' "1+2+3" s0
        (sn, rs) = foldAndPropagateConstants' [("y", parse "5*x + 7"), ("z", parse "x+y-1")] s1 
    in
       (sn, r1 : rs)

-- and

foldAndPropagateConstants' [] s0 = (s0, [])

现在，Generalize!（通过用符号值替换示例值）。

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

Haskell - Using previously computed values in next function calls in a sequence

evaluation

parsing

function

list