Recursion/Pattern Matching to evaluate a Postfix expression in Haskell

Question

I am taking an introduction functional programming class, and we are tasked to evaluate a postfix expression in Haskell using a stack. We have covered pattern matching, guards, and recursion so far however I am still struggling to understand how to use Haskell to achieve this. The input of the project is a [String] array, for example ["59","14","-"] (simplest case). We are tasked to solve this which would be 59-14= 45 and return it as a string. The method stub we are given is shown below called "evaluate". What I understand so far is that if the element in the array is not an operator, I need to push to a stack, which I created a method for called "push" but that is obviously wrong. If the element is an operator I need to pop two numbers from the stack and perform the operation, then push it back on the stack. I also understand that I need to recursively call the function evaluate to see all the input. My question is how do I use a stack in Haskell to push numbers, then pop them when I see an operator. For some reason it does not make sense to me in a functional approach. I am just looking for some guidance on this simplest case so I can build from there. I am not sure how to exactly push to a stack then recursively call my "evaluate" function with the rest of the array. Also apologize if this is a bad post, this is my first time asking on here. Thanks

-- Your implementation goes here. Feel free to add more functions.
evaluate :: [String] -> String
evaluate []  = "" 
evaluate("-":xs) = "-"        
evaluate(a:xs) = do 
         push a []
        --/would I call evaluate here?


push::[String]->[Int]->String
push (x:xs) [] = [x]
--not sure what to do after this 

I have tried to create a method called push, that pushes a number to the stack, but I am not sure how to actually push the element on a stack, then recursively call my evaluate function. Maybe I am thinking about this the wrong way.

Answer 1

Your stack is supposed to return a list: the new stack, so you push an item with:

push:: String -> [Int] -> [Int]
push x xs = read x : xs

or shorter:

push:: String -> [Int] -> [Int]
push = (:) . read

as for the evaluate function, you will need to make use of a helper function that you initialize with an empty stack. You then walk through the list and update the accumulator: the stack until you reach the end of the list of strings to then return the peek of the stack:

evaluate :: [String] -> String
evaluate  = go []
    where go (x:_) [] = …
          go (x1:x2:xs) ("-":ys) = …
          -- ⋮
          go xs (y:ys) = go (push y xs) ys

here for the last line we thus push y on the stack xs and recurse with the new stack as first parameter, and the rest of the items of the list as remaining items. The … and ? parts still need to be implemented.