Skip to main content
added 18 characters in body
Source Link

To evaluate some typed lambda calculus applications, the type of the function might have to be "lifted" in order to match the type of the value it is applied to. For example, in the exponential operator for Church numerals $$\lambda n . \lambda m . m\ n,$$ the $m$ cannot be directly applied to $n$, because $m$ expects a first argument of type

$$a \rightarrow a$$

and $n$ has type

$$(a \rightarrow a) \rightarrow a \rightarrow a.$$

But since the type variable $a$ in $m$ can be any type, it can also be $t = a \rightarrow a$. Then the type of $m$ becomes

$$((a \rightarrow a) \rightarrow (a \rightarrow a)) \rightarrow (a \rightarrow a) \rightarrow (a \rightarrow a).$$

Now, the first argument of $m$ has the right type, so $m$ can be applied to $n$.

In simply typed lambda calculus, we are not allowed to do the type substitution

$$a = a \rightarrow a,$$

but I believe we might be able to interpret it in another manner.

If we view simply typed lambda calculus with one type variable as a category with signatures as objects and terms as arrows, this lifting seems to be a bi-endofunctor $\operatorname L$, from $t$ and $m$, of mixed variance in $t$ and covariant and Cartesian closed in $m$ (is that correct?). My question is: does this bifunctor fulfill some universal property in that category?

To evaluate some typed lambda calculus applications, the type of the function might have to be "lifted" in order to match the type of the value it is applied to. For example, in the exponential operator for Church numerals $$\lambda n . \lambda m . m\ n,$$ the $m$ cannot be directly applied to $n$, because $m$ expects a first argument of type

$$a \rightarrow a$$

and $n$ has type

$$(a \rightarrow a) \rightarrow a \rightarrow a.$$

But since the type variable $a$ in $m$ can be any type, it can also be $t = a \rightarrow a$. Then the type of $m$ becomes

$$((a \rightarrow a) \rightarrow (a \rightarrow a)) \rightarrow (a \rightarrow a) \rightarrow (a \rightarrow a).$$

Now, the first argument of $m$ has the right type, so $m$ can be applied to $n$.

In simply typed lambda calculus, we are not allowed to do the type substitution

$$a = a \rightarrow a,$$

but I believe we might be able to interpret it in another manner.

If we view simply typed lambda calculus with one type variable as a category with signatures as objects and terms as arrows, this lifting seems to be a bi-endofunctor, from $t$ and $m$, of mixed variance in $t$ and covariant and Cartesian closed in $m$ (is that correct?). My question is: does this bifunctor fulfill some universal property in that category?

To evaluate some typed lambda calculus applications, the type of the function might have to be "lifted" in order to match the type of the value it is applied to. For example, in the exponential operator for Church numerals $$\lambda n . \lambda m . m\ n,$$ the $m$ cannot be directly applied to $n$, because $m$ expects a first argument of type

$$a \rightarrow a$$

and $n$ has type

$$(a \rightarrow a) \rightarrow a \rightarrow a.$$

But since the type variable $a$ in $m$ can be any type, it can also be $t = a \rightarrow a$. Then the type of $m$ becomes

$$((a \rightarrow a) \rightarrow (a \rightarrow a)) \rightarrow (a \rightarrow a) \rightarrow (a \rightarrow a).$$

Now, the first argument of $m$ has the right type, so $m$ can be applied to $n$.

In simply typed lambda calculus, we are not allowed to do the type substitution

$$a = a \rightarrow a,$$

but I believe we might be able to interpret it in another manner.

If we view simply typed lambda calculus with one type variable as a category with signatures as objects and terms as arrows, this lifting seems to be a bi-endofunctor $\operatorname L$, from $t$ and $m$, of mixed variance in $t$ and covariant and Cartesian closed in $m$ (is that correct?). My question is: does this bifunctor fulfill some universal property in that category?

Source Link

Does lambda polymorphism have some universal property?

To evaluate some typed lambda calculus applications, the type of the function might have to be "lifted" in order to match the type of the value it is applied to. For example, in the exponential operator for Church numerals $$\lambda n . \lambda m . m\ n,$$ the $m$ cannot be directly applied to $n$, because $m$ expects a first argument of type

$$a \rightarrow a$$

and $n$ has type

$$(a \rightarrow a) \rightarrow a \rightarrow a.$$

But since the type variable $a$ in $m$ can be any type, it can also be $t = a \rightarrow a$. Then the type of $m$ becomes

$$((a \rightarrow a) \rightarrow (a \rightarrow a)) \rightarrow (a \rightarrow a) \rightarrow (a \rightarrow a).$$

Now, the first argument of $m$ has the right type, so $m$ can be applied to $n$.

In simply typed lambda calculus, we are not allowed to do the type substitution

$$a = a \rightarrow a,$$

but I believe we might be able to interpret it in another manner.

If we view simply typed lambda calculus with one type variable as a category with signatures as objects and terms as arrows, this lifting seems to be a bi-endofunctor, from $t$ and $m$, of mixed variance in $t$ and covariant and Cartesian closed in $m$ (is that correct?). My question is: does this bifunctor fulfill some universal property in that category?