operator and function precedence in Haskell

Question

So this does not work:

take 50 iterate (* 2) 1

Because it requires parenthesis in the second argument of take. My question is why.

Haskell rightfully sees a discrepancy in the types:

 Couldn't match expected type `[a0]'
            with actual type (a1 -> a1) -> a1 -> [a1]'

My questions are:

1) It seems that haskell first tries to resolve the take 50 function before the iterate function. Why does haskell do this? When in mathematics if you have f g t w u (x) you first evaluate u(x) before doing anything else. Why does haskell start with evaluating f in this case?

2) Haskell was smart enough to detect that the actual type was:

(a1 -> a1) -> a1 -> [a1]

Now, if it sees that the output of this function is [a1], a type that would unify with the expected type [a0], why does haskell not unify it?

3) why does the $ operator fix this? I know that:

($) :: (a -> b) -> a -> b

So basically what this operator does is say "write FUNCTION $ ARGUMENT" and you get the value of the function evaluated at that argument. In the take 50 case the type is:

take 50 :: [a2]->[a2]
take 50 $ :: a->b 
where a ~a2 and b~b2 then
take 50 $ :: [a2]->[a2]

So basically im in the same situation as in the first case, without using parenthesis or $. This case is i need an argument of the type [a2] (haskell calls it [a0] but its the same. So.. why does haskell unify [a2] with (a1 -> a1) -> a1 -> [a1] when i use $ but it doesnt when i dont use it?

Answer 1

Function application (denoted by "juxtaposition", putting a function and its argument next to each other) has to be parsed somehow, and it needs to be either left-associative or right-associative in order to be parsed unambiguously.¹

Function application is actually left-associative, so what you wrote is equivalent to

((((take 50) iterate) (* 2)) 1)

If it were right-associative instead, you would have

(take (50 (iterate ((* 2) 1))))

That's not what you wanted either, and it's much worse as a default choice: there are very few programs where a right-associative operator would feel more natural.

Since no uniform rule for parsing can produce the program you intend, it's necessary for you, the programmer, to tell haskell what you actually meant, by giving a hint in the form of $ or some parentheses.

As for why $ helps: it is defined to have a very low precedence in parsing, so that writing

take 50 $ iterate (* 2) 1

parses as

(take 50) $ ((iterate (* 2)) 1))

which is actually what you wanted.

¹ Unambiguous parsing is a very desirable property for having understandable programs, and letting the typechecker decide how to parse things (as you suggest it might be able to do) would be quite a mess.

Answer 2

f g t w u (x) is not a sequence of function applications in math either. However, in math, if we take . to be the function composition operator, then (f . g . t . w . u) (x) first applies the u function then the w function and so on. This is the same in Haskell: (f . g . t . w . u) x.

In your first type error, it is trying to unify the type [a0] with the type (a1 -> a1) -> a1 -> [a1], not with the type [a1]. It isn't possible for this to unify, so it gives an error.

Juxtaposition is function application in Haskell, not function composition (incidentally, in math juxtaposition is usually multiplication). This means that an expression like f x y z means (essentially) "apply the function f to the arguments x, y and z". This is equivalent to ((f x) y) z. Each function in Haskell takes exactly one argument. What this means is that something like f x y z = x + y * z is actually the same as f = \x -> \y -> \z -> x + y * z. Function application is left associative so f x y z is the same as writing ((f x) y) z, that is, apply f to x first take the resulting function and apply that to y. Finally, apply that function to z.

This means that your original expression is interpreted as (again, converting to standard math notation): take(50, iterate, (* 2), 1).

Answer 3

take 50 iterate (* 2) 1 would be equivalent in languages with parenthesized-calls with take (50, iterate, * 2, 1), but what you want is take (50, iterate(* 2, 1)). The $ serves exactly the purpose of "open a parenthesis here and close it the most far you can". Its just like calling a function, but right-associative instead of left-associative. You can write it without the $ operator using take 50 (iterate (*2) 1).

Answer 4

Function application is left associative, so

f g a b

is

((f g) a) b

So you have

(((take 50) iterate) (*2)) 1

This is incorrect since it applies take 50 :: [a] -> [a] to iterate which has the type (a -> a) -> a -> [a], clearly incorrect.

Answer 5

(I'll give you a little bit more verbose answer, covering some corners that I think other answers left uncovered, not explicitly at least).

In Haskell, parentheses do not signify function call. They are just for grouping. So u (x) is exactly the same as u x, in Haskell.

The type error you first show is generated by Haskell trying to use iterate as the 2nd argument to take:

take    :: Int -> [a0]                     -> [a0]
take       50     iterate                  :: t 
iterate ::        (a1 -> a1) -> a1 -> [a1]
                  ------------------------
                  [](...) and (->)(...) do not match

It doesn't try to "resolve iterate function after having resolved take 50 function". It hasn't looked at the rest of your long expression yet. It's just trying to use the iterate value. Which happens to be a function.

Functions are just values in Haskell, that's why there's no special syntax for calling them, like there is in various foo(args){exps;}; languages.

For a compiler to try to correct your expressions for you is too dangerous: too many typos or errors would suddenly get unintended meanings. At the most this could be a feature of some hypothetical interactive development environment.

When you write take 50 $ iterate (*2) 1, the type of that second expression (after the $ operator) is

iterate ::        (a1 -> a1) -> a1 -> [a1]
iterate           (*2)          1  :: [Int]  -- it's actually (Num a => [a]) 
                                             -- but that's besides the point

and that list-of-numbers type (:: Num a => [a]) is what gets matched against the 2nd argument in the call to take, not the type of naked non-applied iterate itself:

take    :: Int ->               [a0]       -> [a0]
take       50     (iterate (*2) 1  )       :: t 
iterate (*2) 1    :: (Num a) => [a ]
                  ------------------
                  a0 ~ (Num a)=> a            t ~ (Num a) => [a]

And so it "typechecks", i.e. it works. And indeed, in GHCi we get

Prelude> :t take 50 (iterate (*2) 1 )
take 50 (iterate (*2) 1 ) :: (Num a) => [a]