the behavior of "const id"

Question

I'm working on the 99 Haskell questions and saw a solution for finding the last element of a list:

  myLast = foldr1 (const id)

the type of const is a -> b -> a but that of const id is b -> a -> a
so what's the magic here?

Answer 1

The only way I finally grasped this was to imagine the sequence of steps Haskell takes in evaluating an expression like const id 1 2. First consider these statements:

In Haskell, all functions are considered curried: That is, all functions in Haskell take just one argument. 1

Functional application though, associates to the left: f x y is really (f x) y. 1

With this in mind, and seeing from above that const takes two arguments and id takes one, we can see these steps:

const id 1 2   -- Haskell evaluates 'const id' and returns a function (we can call it
               -- 'constId') which accepts one argument and always returns 'id'

constId 1 2    -- Haskell now evaluates 'constId 1', which as expected just returns 'id'

id 2           -- 'id' is now applied to 2, which just returns '2'

2              -- final result

Disclaimer: I am new to Haskell.

Answer 2

No magic. The definition of const is:

const :: a -> b -> a
const x y = x

And the definition of id is:

id :: a -> a
id x = x

So const id is just \y -> id, a function that always returns id. And if id is just \x -> x then const id must be the same as \y -> \x -> x. Ergo, it has type b -> (a -> a).

const id can also be written flip const. Since const is \x -> \y -> x, then flip const takes the arguments in the opposite order, \y -> \x -> x, which is the same as const id.

Answer 3

Here's my understanding of how this works.

This is the simplest explanation I could think of, I tried (on purpose) to avoid any potentially confusing concepts or words.

An important concept to keep in mind is partial application.

The way I understand this is, that in Haskell we can “fix” one of the parameters of the function to a known value, so now the function accepts one less parameter.

Recap: the type of const is:

const :: a -> b -> a

As a simpler example, let's “fix” the first parameter to be (+)

let f = const (+)

Now that we've fixed the first parameter of const, “f” is a function which accepts only a single parameter. But since const always return its first parameter, which we've fixed, it means that whatever we pass to “f” will be ignored, and it will always return the function “+”.

As an example, all the following will give 5, since f will always return the function “+” regardless of what it received as the first parameter, and the function “+” will operate on 2 and 3:

f “aaa”        2 3
f  904212      2 3
f  undefined   2 3

The type of f is:

f :: b -> Integer -> Integer -> Integer

Note that “b” can be anything, as can be seen above.

Now for the actual function in question:

g = const id

This means that we “fixed” id as the first parameter, so as above, “g” ignores its first parameter and returns the function “id”. In Haskell, we can go on ahead and provide the extra parameter to “id”, just like we did to (+) above, so for example all of these will return 42:

g  “aaa”     42
g  undefined 42

So “g” is function accepting two parameters, and always returning the second one, so its type is:

g = const id :: b -> a -> a

But wait a minute, I just made a giant leap there. Shouldn't the type be:

b -> (a -> a) 

since we just said that we accept anything and return “id”?

Well, yeah, except that in Haskell those parentheses can be omitted.
It also make sense since you can immediately supply the “id” function with the extra parameter it needs (as in the “const (+)” example above).

Answer 4

The type of id is c->c; it just returns the same thing it is given.

The type of const is a->b->a. In const id, a becomes c->c, so the type of const in this case becomes:

(c->c) -> b -> (c->c)

Now that you have applied this const function, i.e. you have passed id to it, then you are left with b -> (c->c).

PS: The type of const const id is a->b->a, and the type of const const const id is b->a->a, and so on!