Haskell Function Returning Empty List

Question

I'm really an absolute newbie at Haskell, so I'm at a total loss as to how to debug some functions I wrote. When I call shuntingYard ["3+4"] I get back [], whereas I want to get back [34+]. Any and all help would be greatly, greatly appreciated.

import Char

isOperator :: Char -> Bool
isOperator x = elem x ['+','-','*','/','%','^','!','=','<','>']

associativityOf :: Char -> String
associativityOf x = if elem x ['+','-','*','/','%']
                    then "Left"
                    else "Right"

precedenceOf :: Char -> Int
precedenceOf x
    | elem x "=<>"   = 1 
    | elem x "+-"    = 2
    | elem x "*/%"   = 3
    | elem x "^!"    = 4
    | otherwise      = 0

operatorActions :: [[Char]] -> [[Char]] -> [[Char]]
operatorActions stmt stack
    | ( tokenAssoc == "Left"  && tokenPrecedence <= stackPrecedence ) ||        
      ( tokenAssoc == "Right" && tokenPrecedence <  stackPrecedence ) =
        [stackOper] : _shuntingYard stmt (tail stack)
    | otherwise   = _shuntingYard (tail stmt) ((head stmt) : stack)
    where tokenAssoc       = associativityOf (head (head stmt))
          tokenPrecedence  = precedenceOf    (head (head stmt))
          stackOper        = if (not (null stack))
                           then (head (head stack))
                           else '='
          stackPrecedence  = precedenceOf stackOper

stackOperations :: [[Char]] -> [[Char]]                                
stackOperations stack
    | ((not (null stack)) && (head (head stack)) == '(') = 
      error "Unbalanced parens."
    | null stack = []
    | otherwise  = (head stack) : _shuntingYard [] (tail stack)

_shuntingYard :: [[Char]] -> [[Char]] -> [[Char]]
_shuntingYard stmt stack
    | null stmt          = stackOperations stack
    | all isDigit (head stmt) = (head stmt) : _shuntingYard (tail stmt) stack
    | isOperator  (head (head stmt)) = operatorActions stmt stack
    | (head (head stmt)) == '('=
      _shuntingYard (tail stmt) ((head stmt) : stack)
    | (head (head stmt)) == ')' = if (head (head stack)) == '('
                            then _shuntingYard (tail stmt) (tail stack)
                            else (head stack) : _shuntingYard stmt (tail stack)
    | otherwise = _shuntingYard (tail stmt) stack

shuntingYard :: [[Char]] -> [[Char]]
shuntingYard stmt = _shuntingYard stmt []

Answer 1

As a general debugging technique, you can use the Debug.Trace module to find out which functions are being called and what their inputs are. Using look at the state of your algorithm after each step.

import Debug.Trace

-- Show arguments each time _shuntingYard is called
_shuntingYard :: [[Char]] -> [[Char]] -> [[Char]]
_shuntingYard stmt stack = traceShow (stmt, stack) $ __shuntingYard stmt stack

__shuntingYard stmt stack
  | null stmt = stackOperations stack
  {- etcetera -}

This prints:

(["3+4"],[])
([],[])

Hmm, you lost everything after the first call. Looking at the guards in __shuntingYard, it seems that the "otherwise" case gets called.

Maybe you wanted to call shuntingYard ["3", "+", "4"]?

Answer 2

Ok, let's just play through what happens when you call shuntingYard ["3+4"]:

1. It calls _shuntingYard ["3+4"] []
2. It goes through the guards of _shuntingYard:
   1. null stmt = null ["3+4"] = false
   2. all isDigit (head stmt) = all isDigit "3+4" = false as + is not a digit
   3. isOperator (head (head stmt)) = isOperator '3' = false
   4. Also false as '3' /= '('
   5. Also false as '3' /= ')'
3. Since none of the guards matched, so we go into the default case and call _shuntingYard (tail stmt) stack = _shuntingYard [] []
4. This time the first guard(null stmt = null []) matches, so we call stackOperations [] and get [].