Haskell - Использование ранее вычисленных значений в следующих вызовах функций в последовательности - PullRequest
Новая
       10

Haskell - Использование ранее вычисленных значений в следующих вызовах функций в последовательности

0 голосов
/ 28 марта 2020

Я пытаюсь создать функцию для арифметических операций с синтаксическим деревом c, и до сих пор я почти достиг цели. В прилагаемом коде вы можете увидеть мои текущие определения функций. 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 _ = []

Ответы [ 2 ]

3 голосов
/ 28 марта 2020

Редактировать: Кажется, я ответил только на эту часть вопроса:

Не могу найти способ использовать значение "x" в моем eval function.

Поскольку ваш вопрос не включает минимальный воспроизводимый пример , здесь приведена упрощенная версия того, что вы, кажется, делаете (не содержит переменных), которая оба содержат определение 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 и расширение функции 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 использует более безопасный тип возврата Maybe, который будет способствовать перезаписи, которую я предлагаю: 

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)

I Я использовал разные стили в каждом теле функции, но все они являются вариантами схожей темы: case-of использует явное сопоставление с образцом, что утомительно. (Представьте, что вы делаете тело eval (BinOp ...) с использованием case-of.) Явное использование оператора >>= - это ... Я полагаю, что некоторым это нравится, но запись do выглядит красивее. Я думаю, что <$> аппликативный стиль - самый лучший из них в этом случае.

Что вы могли бы сделать дальше, это сделать неявным env с помощью монады Reader : Немного запутанно, что только одно тело функции в eval фактически использует его, а все остальные либо выбрасывают его, либо передают.

2 голосов
/ 29 марта 2020

Вы хотите, чтобы 

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

А теперь, Обобщение! (путем замены значения примера символом c единица).

...