Here are 10 function signatures that have infinite inhabitants, similar to ∀ x. (x -> x) -> x -> x:
-
∀ x y. (x -> y) -> x -> y: This is a function that takes a function from x to y, an x, and returns a y. It has infinite inhabitants because there are infinite ways to map x to y.
-
∀ x. (x -> x -> x) -> x -> x: This function takes a binary function (a function that takes two x and returns an x), an x, and returns an x.
-
∀ x y z. ((x -> y) -> (y -> z)) -> x -> z: This function takes a composition of two functions (one from x to y and another from y to z), an x, and returns a z.
-
∀ x. (x -> x) -> (x -> x) -> x -> x: This function takes two unary functions (functions from x to x), an x, and returns an x.
-
∀ x y. (x -> y -> y) -> x -> y -> y: This function takes a binary function (a function from x and y to y), an x, a y, and returns a y.
-
∀ x y. (x -> x) -> (y -> y) -> x -> y -> y: This function takes two unary functions (one from x to x and another from y to y), an x, a y, and returns a y.
-
∀ x y. (x -> x) -> (x -> y) -> x -> y: This function takes two functions (one from x to x and another from x to y), an x, and returns a y.
-
∀ x y. (x -> y) -> (y -> x) -> x -> y: This function takes two functions (one from x to y and another from y to x), an x, and returns a y.
-
∀ x y z. (x -> y) -> (y -> z) -> (z -> x) -> x -> z: This function takes three functions (one from x to y, one from y to z, and one from z to x), an x, and returns a z.
-
∀ x y z. (x -> y -> z) -> x -> y -> z: This function takes a binary function (a function from x and y to z), an x, a y, and returns a z.
Each of these function signatures has infinite inhabitants because for each one, there are infinite ways to map the inputs to the outputs Source 4.