Skip to content

Instantly share code, notes, and snippets.

@freeman42x
Created September 12, 2023 05:54
Show Gist options
  • Save freeman42x/cf96f63a5e874d77671842624eede9cd to your computer and use it in GitHub Desktop.
Save freeman42x/cf96f63a5e874d77671842624eede9cd to your computer and use it in GitHub Desktop.
10 function signatures that have infinite inhabitants

Here are 10 function signatures that have infinite inhabitants, similar to ∀ x. (x -> x) -> x -> x:

  1. ∀ 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.

  2. ∀ 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.

  3. ∀ 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.

  4. ∀ x. (x -> x) -> (x -> x) -> x -> x: This function takes two unary functions (functions from x to x), an x, and returns an x.

  5. ∀ 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.

  6. ∀ 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.

  7. ∀ 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.

  8. ∀ 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.

  9. ∀ 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.

  10. ∀ 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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment