Haskell function composition using foldl

Question

I have defined the following function in haskell:

step :: [Int] -> [Char] -> [Int]
step stack str
    | str == "*" =  remaining ++ [x*y] 
    | str == "+" =  remaining ++ [x+y]
    | str == "-" =  remaining ++ [x-y]
    | str == "/" =  remaining ++ [x `div` y]
    | otherwise = stack ++ [read str :: Int] 
    where x = (last . init) stack
          y = (last stack)
          remaining = (init . init) stack

This functions takes and integer array [10, 4, 3] and a string operator * and applies the operator to the last two items in the array and returns the following array [10, 7].

This is makes up part of an intermediary function, the end result is a reverse polish notation evaluator function.

How can I utilise the step function I've defined and foldl to do the following:

Take the examples string: "10 4 3 + 2 * -".

Add each element onto the string until the first operator is encountered as so:

10, 4, 3 Then apply the operator to the two elements onto top the stack and place the result on the stack:

10, 7.

Continue as so until the final answer is evaluated (-4)

Answer:

For the sake of completeness this was the function I arrived at with the help of @talex

rpn :: String -> Int
rpn input = head result
    where arr = words input
          result = foldl step [] arr

Regardless of anything, you are using the list backwards. The natural way to implement a stack is to have the stack top at the head of the list, not at the end. — n. 1.8e9-where's-my-share m.
Stack operations map 1:1 to primitive list operations. empty = []; top = head; push = (:); pop = tail. All of those are O(1). last, init and (++) are not primitive operations, all of them are O(N). — n. 1.8e9-where's-my-share m.

talex talex · Accepted Answer · 2019-01-03T07:58:15

foldl step [] ["10",  "4", "3", "+", "2", "*", "-"]

[] here is initial stack.

If you rewrite your step in the following way it will work faster:

step :: [Int] -> [Char] -> [Int]
step stack str
        | str == "*" =  (x*y):remaining 
        | str == "+" =  (x+y):remaining
        | str == "-" =  (x-y):remaining
        | str == "/" =  (x `div` y):remaining
        | otherwise = (read str :: Int):stack
        where x = head $ tail stack
              y = head stack
              remaining = tail $ tail stack

Haskell function composition using foldl

1 Answers