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

Question

I'm trying to make a function for syntax tree arithmetic operations and thus far I'm almost where I want it to be. In the code I attach you can see my current function definitions. eval is the function that decides what to do with each operation and foldAndPropagateConstants is the main function. parse is a simple parser that takes a String of a mathematical expression and returns the equivalent tree. e.g.

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

The issue I'm facing is how to have the evaluated values to be used in subsequent operations. For example, this operation should work as follows:

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

Notice that the function should use the value that "x" got, when calculating the value for "y". Thing is, I can't seem to find a way to use "x"'s value in my eval function.

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

Edit: I seem to have answered only this part of the question:

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

Since your question does not include a Minimal, Reproducible Example, here is a simplified version of what you seem to be doing (that doesn't contain variables) that both contains the data definition and the eval function:

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

Extending this evaluator with another constructor in data Expr, and extending the eval function with an "environment" as luqui suggests, which in this case is a list of name-value pairs:

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

It seems to me that the most urgent improvement to this evaluator is better error handling using error-aware return types. I made the lookup' helper function because the standard library function Data.List.lookup uses the safer Maybe return type which would encourage the rewrite I'm suggesting:

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've used a different style in each function body, but they're all variations of a similar theme: case-of uses explicit pattern matching, which gets tedious. (Imagine doing the eval (BinOp ...) body using case-of.) Explicit use of the >>= operator is... I suppose some people like it, but do notation looks prettier. The <$> applicative style is the neatest of them all in this case, I think.

What you could do next is make the env implicit by using the Reader monad: It is a bit messy that only one function body in eval actually uses it, and all the others either throw it away or pass it along.

Answer 2

What you want is for

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

to be equivalent to

 =  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' is like parse, but it can also consult a store of values known so far which it receives as its second argument.

The above is easier encoded with functions if restructured as

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

Incidentally this pattern of state-passing computations is known as State Monad, but that's a matter for another day.

The above fits the recursion pattern when expressed as

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

And now, Generalize! (by replacing an example value with a symbolic one).