Why isn't (b) of (a -> (b -> c)) the first parameter in the function definition but the second in type signature?

Question

If first parameter is taken by the function first as function application is left-associative, for example:

drop 2 [1,2,3,4]

result: [3,4]

is equivalent to

(drop 2) [1,2,3,4]

same result: [3,4]

Here my question is, if the type signature is right-associative, which means, things in right side evaluate first, in this case, it's gonna be as follows, as the first parameter is first taken by the function:

drop :: [1,2,3,4] -> (2 -> [3,4])

It shouldn't have been as follows, right?

drop :: Int -> ([a] -> [a])
drop :: 2 -> ([1,2,3,4] -> [3,4])

So, why does it take the second parameter first in type signature of the function instead of the first parameter?

In addition, if the second parameter is evaluated prior to first parameter, then why is the following usage invalid?

(drop [1,2,3,4]) 2

Scarron

Sorry, don't understand your question. You are already seeing it being processed as (drop 2) ([1,2,3 4] -> [3,4]) right? – Buoyancy

@Buoyancy Hi! I mean, For example: (drop 2 [1,2,3,4]), if the first parameter of the function definition get evaluated first because it's left-associative, but it shows in type signature as "drop :: Int -> ([a] -> [a])" , which means the list [1,2,3,4] as the second parameter will be evaluated first before the Int 2, right? But why can we also write a syntax like this ((drop 2) [1,2,3,4]) ? It is apparent that the first parameter (2) will be evaluated first instead of the second parameter ([1,2,3,4]) shown in type signature. – Scarron

The fact that the type signature is right associative does not mean that function application is right associative. – Acrodrome

@WillemVanOnsem So, the complier may not evaluate the (drop 2) first because it's lazy evaluation, as it will look at the whole as ((drop 2) [1,2,3,4]), and then first evaluate the ([a] -> [a]) part which is ([1,2,3,4] -> [3,4]), as it's right-associative? – Scarron

@Akari: the fact that it is lazy does not matter, since the type system itself is eager: the Haskell compiler determines at compile time the type of each subexpression. It thus can reason what the type of drop 2 is. It thus evaluates (drop 2) which has type [a] -> [a], and that function is then applied to [1,2,3,4]. – Acrodrome

If that's true, it's very confusing at first look, to be honest. – Scarron

@Scarron it is indeed confusing at first, but you'll quickly get used to it and then it will feel very obvious. – Qp

Same reason putStrLn "foo" >> (putStrLn "bar" >> putStrLn "baz") prints "foo" first even though putStrLn "bar" is in brackets. – Unboned

Associativity and evaluation order are not related. Associativity is about how the parser resolves a grammar ambiguity when choosing a term to execute at compile-time; evaluation order is about how the execution engine processes a term at run-time. One controls how you produce a term, the other controls how you consume a term. – Kettering

Answer 1

It's nonsensical to write things like drop :: [1,2,3,4] -> (2 -> [3,4]) or 2 -> ([1,2,3,4] -> [3,4]) – you're mixing type-level and value-level notations there. What you should instead do is look at local types of subexpressions:

drop                  2    [1,2,3,4]
└─┬┘                  ┊    └──┬────┘
┌─┴───────────────┐ ┌─┴─┐  ┌──┴──┐
│Int->[Int]->[Int]│ │Int│  │[Int]│
└─────────────────┘ └───┘  └─────┘

Add the implied parentheses

(drop                   2)    [1,2,3,4]
 └┬─┘                   ┊     └──┬────┘
┌─┴─────────────────┐ ┌─┴─┐   ┌──┴──┐
│Int->([Int]->[Int])│ │Int│   │[Int]│
└───────────────────┘ └───┘   └─────┘

Now the subexpression drop 2 means you're applying the argument 2 as the first argument of the function drop, i.e. as the Int in its signature. For the whole drop 2 expression, this argument has therefore vanished:

(           drop           2   )  [1,2,3,4]
┊  ┌──────────┴────────┐ ┌─┴─┐ ┊  └──┬────┘
┊  │Int->([Int]->[Int])│ │Int│ ┊     ┊
┊  └───────────────────┘ └───┘ ┊     ┊
└────────────┬─────────────────┘  ┌──┴──┐
        ┌────┴───────┐            │[Int]│
        │[Int]->[Int]│            └─────┘
        └────────────┘

This is analogous to applying the single-argument function length :: [Bool] -> Int to the single argument [False,True] :: [Bool] to get the result length [False,True] ≡ (2::Int). The fact that for drop the result has type ([Int]->[Int]) instead of something “atomic” like Int is irrelevant at this stage.

Then on the outer level, you're applying the function of type [Int]->[Int] to the argument of type [Int], which is perfectly sensible. The whole thing then has simply result type [Int].

( (           drop           2   )  [1,2,3,4] )
┊ ┊  ┌──────────┴────────┐ ┌─┴─┐ ┊  └──┬────┘ ┊
┊ ┊  │Int->([Int]->[Int])│ │Int│ ┊     ┊      ┊
┊ ┊  └───────────────────┘ └───┘ ┊     ┊      ┊
┊ └────────────┬─────────────────┘     ┊      ┊
┊         ┌────┴───────┐            ┌──┴──┐   ┊
┊         │[Int]->[Int]│            │[Int]│   ┊
┊         └────────────┘            └─────┘   ┊
└────────────────────────┬────────────────────┘
                      ┌──┴──┐
                      │[Int]│
                      └─────┘

Qp

Great answer, this is probably the clearest I've seen this explained to beginners. – Illimitable

Answer 2

I think you misunderstand what right associative means. It indeed means that:

drop :: Int -> [a] -> [a]

is equivalent to:

drop :: Int -> ([a] -> [a])

This thus means that drop is a function that takes a parameter of type Int, and then returns a function of type [a] -> [a].

But function application itself is left-associative. Indeed:

drop 2 [1,2,3,4]

is short for:

(drop 2) [1,2,3,4]

Here drop 2 will thus return a function of type [a] -> [a] that will drop the first two items of the list. We then apply [1,2,3,4] to that function, and thus obtain [3,4].

Acrodrome

Thanks for reply, sir! So, the function actually first takes the first parameter, and then generates the second function that takes the second parameter in either expressions (drop 2 [1,2,3,4]) or ((drop 2) [1,2,3,4])? – Scarron

@Scarron notice that drop 2 [1,2,3,4] is short for (drop 2) [1,2,3,4], in other words, they are the exact same expresion. Same thing happens with arithmetic expressions: 9 / 3 / 3 is exactly the same as (9 / 3) / 3 because arithmetic operations are left assoc. – Acidulate

@Ismor yes, you're right – Scarron

@Scarron Yes, you can pretend that f x y with f :: A -> B -> C first takes f x and computes a result which is a function B -> C, and then this result function is applied to y resulting in some value of type C. So, it's evaluated as (f x) y and the type actually means A -> (B -> C). – Arse

Keep in mind that (->) itself is an operator (but at the type level, rather than the term level) not just syntax in a function signature. You can use :info (->) to see its kind, precedence, and associativity, and you can assign the result to a name (which is what type ... = ... does). – Cousin

Answer 3

I guess I've understood the puzzle now:

In a function application, the function will always take parameters from left to right, one by one, as it's left-associative. Its purpose is to substitute the bound variables with parameters.

Now, when it comes to type signature of the function, it's right-associative indeed, but it doesn't mean the function will be applicated by taking the last argument, then the second last argument, and so forth.

A function application:

((((a) b) c) d) e

means that the following expressions have the following types:

a :: b -> (c -> (d -> e))
a    b ::  c -> (d -> e)
(a   b)    c ::  d -> e
((a  b)    c)    d :: e

this can be read as: The function takes first parameter (b) and returns the second function (c -> (d -> e)), that takes second parameter (c) and returns the third function (d -> e) that takes third parameter (d) and returns the final result (e).

As @Daniel Wagner pointed out:

The associativity order doesn't mean the evaluation order of the function.

In this case, the right-associative in type-signature is equivalent as follows, a pair of parentheses (c -> d) means a returned function by the function that takes the (b) from left side:

a :: b -> (c -> d)

As functions in Haskell are based on Lambda calculus, here I'll use lambdas since I'm familiar with them, as examples:

Original version:

  (λab.a+b) (1,2)
= (a+b)[a:=1,b:=2]
= 1+2
= 3

But since an abstraction in Lambda calculus that only takes one input in each step, it can be rewritten into:

Curried version:

  (λa.(λb.a+b)) 1 2
= ((λb.a+b)[a:=1]) 2
= (λb.1+b) 2
= (1+b)[b:=2]
= 1+2
= 3

Note: Terms or logic of this post may be incorrect. If you are able to and wish, you could edit my post to correct it. :)

Scarron

the curried form is (λa.(λb.a+b)) 1 2 = ((λb.a+b)[a:=1]) 2 = (λb.1+b) 2 = (1+b)[b:=2] = 1+2 and the uncurried form is (λ(a,b).a+b) (1,2) = (a+b)[a:=1,b:=2] = 1+2. – Natoshanatron

the type of the second function is (a,a) -> a, and the type of the first is a -> (a -> a): having received the first a argument, it returns the function of the type (a -> a) which is the same as a -> a -- the parens are used for grouping only and by convention are redundant even in the first variant since -> is considered to be right associative. an infix operator * being "right-associative" means, x*y*z*w is interpreted as x*(y*(z*w)). (all the as are actually Num => a, but that's not important right now). – Natoshanatron

@WillNess You're right about to point out my mistakes, but I think in lambda calculus, even an uncurried abstraction that takes a 2-tuple should be reworked into a curried abstraction that takes only one input by each step(a 2-tuple is considered two inputs), since in lambda calculus, an abstraction shall take only one 'input'. So I'm gonna eliminate the evaluation steps of the uncurried version, but indicate that is equivalent to the curried version. The Link to Wikipedia – Scarron

Yes, but it was you that wrote it that way, so I used your approach for an illustration. The goal is to show you a correct version, not to point out the mistakes. – Natoshanatron

Since the first parameter (b) is taken by the function in first step to return the second (c -> (d -> e)), that takes (c) and returns (d -> e). How would it be called right associative? Are there any resources on the internet that explain this? – Scarron

"association" refers to how an expression without explicit parentheses is parsed. If 1•2•3•4 is taken to actually stand for 1•(2•(3•4)) this is referred to as • being "right assotiative" because the grouping is done on the right of •. There have to be parens there because this imagined infix operator • is a binary infix operator. Same goes for ->. – Natoshanatron

Now supposed we defined (a•b) = if a==0 then 0 else a*b. This would mean evaluating x•y would first evaluate the expression to the left of •, and only if it were found to be non-zero would it try to evaluate the expression to the right of •. – Natoshanatron