CODEWITHSUNDEEP
haskellfunctional-programmingpostfix-notation
CertainlyNotAdrian
CertainlyNotAdrian

Reputation: 377

haskell reverse polish notation

being new to haskell I decied to try and implement a mini reverse polish notation function:

Takes in a list of type int and a string operator ('*','+','/','-')

apply the operator to the tail element and the tail-1 element

return the resultant list with the two elements involved in the operation popped off and the resultant element appended to the tail as such:

Where e0 = original element at index 0

r = result of the operation:

result = [e0,e1,e2...r] (elements popped off: eN, eN-1)

This is the code I have so far:

import Data.List
import System.IO

step :: [Int] -> String -> [Int]
step stack operator
    | (x:y:ys) "*" = (x * y):ys
    | (x:y:ys) "+" = (x + y):ys
    | (x:y:ys) "-" = (x - y):ys
    | (x:y:ys) "/" = (x / y):ys

And it gives me the following compile error:

• Couldn't match expected type ‘[Char] -> Bool’
                  with actual type ‘[a3]’
    • The function ‘x : y : ys’ is applied to one argument,
      but its type ‘[a3]’ has none
      In the expression: (x : y : ys) "/"
      In a stmt of a pattern guard for
                     an equation for ‘step’:
        (x : y : ys) "/"

I believe this is the result of an error in my syntax, any help is welcome!

Upvotes: 2

Views: 1640

Answers (1)

bradrn
bradrn

Reputation: 8467

You've implemented the function correctly, but your syntax is slightly wrong - you've used guards when you want to use pattern matching:

  • Pattern matching is used when you want to decompose a parameter into smaller parts or treat it in several cases; whereas
  • Guards are used when you want to select one branch of a function based on a boolean condition, similarly to an if/then/else expression. (So the condition of a guard has to be a valid expression of type Bool.)

In your code, you've used guards, but you really want pattern matching, like this:

step :: [Int] -> String -> [Int]
step (x:y:ys) "*" = (x * y):ys
step (x:y:ys) "+" = (x + y):ys
step (x:y:ys) "-" = (x - y):ys
step (x:y:ys) "/" = (x / y):ys

However, this will still give an error:

* No instance for (Fractional Int) arising from a use of `/'
* In the first argument of `(:)', namely `(x / y)'
  In the expression: (x / y) : ys
  In an equation for `step': step (x : y : ys) "/" = (x / y) : ys

This error is fairly clear: you're trying to / an integer, but integers are not Fractional, so you can't do that. If you want integer division, you can replace it with div x y, otherwise you can change Int to Float in the type signature to allow non-integer values.

However, even after this change, there is still a subtle bug: what happens if your list has less than two elements, or an unsupported operator is used? The correct thing to do here is to pattern match at the end by using step _ _ = (something), where _ is a special syntax which matches anything. (Or you can also use step stack operator = (something), if you want to refer back to stack and operator for something like an error message.

EDIT: In the comments below @chepner suggested another way to do this using both pattern matching and guards:

step :: [Int] -> String -> [Int]
step (x:y:ys) op
    | op == "*" = (x * y):ys
    | op == "+" = (x + y):ys
    -- etc.
    | otherwise = (some error case)

This again illustrates the difference between the two: pattern matching is used to decompose the first argument into x, y and ys, while guards are used with boolean conditions (with otherwise actually being defined in the Prelude as being equal to True).

Upvotes: 3

Related Questions