How can a haskell function work if the function ignores its 1st arg?

user_2242556 0
Viewed 122

My question regards the code in the Answer of the question at Haskell - Reverse polish notation regular expression to expression tree. I've duplicated the code here so you needn't follow the above link:

data Tree
  = Symbol Char
  | Op Char Tree Tree
  deriving Show

type Stack = [Tree]

step :: Stack -> Char -> Stack
step (r:l:s) '.' = (Op '.' l r):s
step (r:l:s) '+' = (Op '+' l r):s
step s c         = (Symbol c):s

parse :: String -> Stack
parse = foldl step []

I put the code above in a file, added main that calls parse with arg "aa.bb.+" and got result matching that at the original question.

My question: How does parse work if its 1st arg (the expression to be parsed) is ignored? How can step work if it doesn't receive its second arg?

In my file I replaced:

parse = foldl step []

with:

parse s = foldl step [] s

Resulting program also works correctly and seems "more correct" since parse now uses its arg.

haskell
3 Answers

parse does not ignore its argument. To a first approximation, the expressions \x -> f x and f mean the same thing whenever both typecheck; similarly, to a first approximation, the definitions f = g and f x = g x mean the same thing whenever both typecheck.

Okay, okay, maybe you don't like my bare assertion. Here's another argument you may find convincing. Consider this expression:

parse "aa.bb.+"

If we take the equality parse = foldl step [] seriously, then this should be the same thing as

foldl step [] "aa.bb.+"

simply by substituting one side of the equation for the other. This foldl expression patently does not ignore the final string.

user_7916040

All functions in Haskell take a single argument; ones that appear to take multiple arguments really return another function, not the "ultimate" return value. That is, foldl step [] is not a single call to foldl; it's one call to foldl, and then another call to the function that foldl step returns. Because function application is left-associative, you can write foldl step [] instead of (foldl step) [].

user_11268410
user_171376660
Related