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
3

There are 3 answers

5
willeM_ Van Onsem On

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].

1
leftaroundabout On

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]│
                      └─────┘
7
Akari On

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. :)