Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Identity function in Haskell has multiple inhabitants?

In category theory it can be proven that the identity function is unique. It is also said that, reasoning with parametricity, that the type forall a. a -> a has only one inhabitant. In Haskell though I can think of more implementations of the identity function:

id x = x
id x = fst (x, "useless")
id x = head [x]
id x = (\x -> x) x
id x = (\x -> (\x -> x) x) x

How can I understand the statement "the identity function is unique" and "any function with type forall a. a -> a has only one inhabitant" when there are multiple implementations?

like image 529
Labbekak Avatar asked Apr 29 '20 08:04

Labbekak


People also ask

What does ID function do Haskell?

id , the identity function, is a function with type a -> a that returns its argument unchanged. const takes two arguments, discards the second and returns the first.

What is the identity function used for?

Identity functions are mostly used to return the exact value of the arguments unchanged in a function. An identity function should not be confused with either a null function or an empty function. Here are the important properties of an identity function: The identity function is a real-valued linear function.


Video Answer


2 Answers

Those all look like the same single inhabitant to me. To show that they are different, try to construct an input for which they behave differently. If you cannot, they must in fact be the same function implemented differently.

Consider an analogue from a different discipline. In number theory, it can be proven that there is one unique smallest prime, namely 2. But how can this be? 10/5 is also the smallest prime, as is 1+1. It is possible for all of these statements to be true at once because 10/5 is in fact the same thing as 2, just as all the expressions you've written are the same thing as the identity function.

like image 140
amalloy Avatar answered Sep 28 '22 07:09

amalloy


Those are different implementations of the same function. Thus there is no more then a single inhabitant here as this refers to the function, not to its implementation.

like image 40
michid Avatar answered Sep 28 '22 08:09

michid