What is the rationale for type fx = fx in Haskell?

Haskell gives fx = fx type t1 -> t , but can anyone explain why?

And is it possible for any other, nonequivalent function to have the same type?

+4
source share
2 answers

Well, starting with defining the function fx = fx , skip and see what we can infer about type f .

Start with a completely undefined variable of type a . Can we deduce more than that? Yes, we notice that f is a function that takes one argument, so we can change a to a function between two unknown variables of the type that we will call b -> c . Regardless of type, b means the type of argument x , and any type of c means that it must be the type of the right side of the definition.

What can we understand about the right side? Well, we have f , which is a recursive reference to the function we are defining, so its type is still b -> c , where both type variables are the same as for the definition of f . We also have x , which is a variable associated in the definition of f and is of type b . Applying checks like f to x , because they use the same unknown type b , and the result is c .

At this point, everything is combined and without any other restrictions, we can make type variables β€œofficial”, as a result we get a final type b -> c , where both variables are ordinary, implicitly universally quantized type variables in Haskell.

In other words, f is a function that takes an argument of any type and returns a value of any type. How can he return any possible type? It cannot, and we can notice that its evaluation provides only infinite recursion.

For the same reason, any function with the same type will be "equivalent" in the sense of never returned in evaluation.

An even more direct version is to completely remove the argument:

 foo :: a foo = foo 

... which is also universally quantitative and represents the meaning of any type. This is pretty much equivalent to undefined .

+16
source
 fx = undefined 

has (alpha) equivalent type f :: t -> a .


If you're interested, a system like Haskell comes from Hindley-Milner . Unofficially, typechecker starts with the most permissible types for everything and unifies the various constraints as long as it remains unchanged (or not). In this case, the most common type is f :: t1 -> t , and there are no additional restrictions.

Compare with

 fx = f (fx) 

which deduced the type f :: t -> t due to the union of the types of the argument f on LHS and the argument external f on RHS.

+7
source

Source: https://habr.com/ru/post/1337711/


All Articles