Function application, precedence, and composition

[tomhepz]

Given that haskell uses Polish(/Prefix) notation, the linked wikipedia page states:

'It does not need any parentheses as long as each operator has a fixed number of operands.'

However when trying to write:

butlastbroken :: [a] -> a
butlastbroken xs = head tail reverse xs

This fails however the above quote still applies, each function takes exactly 1 operand and all are applied to 1 operand. It's clear from the type definitions that reverse should take xs and tail should take the output of that... i.e.

butlast :: [a] -> a
butlast xs = head (tail (reverse xs))

Why can't the compiler check this? The example given in the wikipedia page
infix --- (5 − 6) × 7 = × − 5 6 7 --- postfix

Similarly, why is this sugar a valid solution?

butlast' :: [a] -> a
butlast' = head.tail.reverse

[wence-]

This is a good question. I think the rationale is something like the following. Because Haskell is not purely prefix (you can have infix operators like + and * with different precedence), then to parse the textual representation into a syntax tree in an unambigous way needs us to know the types of all the symbols. But to do this, we need the parse tree.

So instead, we define the parsing phase, where the textual representation (the code) is turned into a syntax tree for further analysis with a set of precedence rules. A consequence of the convention for curried functions (that -> is right-associative) is that we want left-associative function application. Hence when parsing (and we don't know the types) we parse

head reverse tail

as

((head reverse) tail)

Which will then fail to type check because (amongst other things) reverse has type [a] -> [a] (not [a])

As you note, you can get around this by parenthesising, like so

butlast :: [a] -> [a]
butlast xs = head (tail (reverse xs))

One way to avoid so many parens, if you're naming the variable, is to use the infix operator ($) :: (a -> b) -> a -> b which is defined like so

($) :: (a -> b) -> a -> b
f $ x = f x
infixr 0 $

So this defines a right-associative function application (the infixr line) with very low precedence. Normal function application has precedence 10 (all binary operators are defined to have precedence in [0..9]).

So now we can write

butlast :: [a] -> [a]
butlast xs = head $ tail $ reverse xs

Finally, you ask why the sugar

butlast :: [a] -> [a]
butlast = head . tail . reverse

works. This is because (.) :: (b -> c) -> (a -> b) -> a -> c is actually function composition. Its definition is

(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)

So let's parenthesise and desugar

head . tail . reverse
== (.) ((.) head tail) reverse
== (.) (\x -> head (tail x)) reverse
== \y -> (\x -> head (tail x)) (reverse y)
== \y -> head (tail (reverse y))

Which is where we started.

The nice thing about the function composition approach is that we don't need to explicitly refer to the variable that the function is acting on. This is termed pointfree style, the Haskell wiki page has some explanation of the name, and details of why it's nice.