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.
CodePudding user response：
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.
CodePudding user response：
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) [].
CodePudding user response：
This is also known as pointfree or tacit programming where a single argument function doesn't have that argument explicitly stated.
Also nifty: site that lets you convert code to pointfree style