leanprover / leanprover/reference-manual

Axioms and Classes disagree on parametricity

Open Beginner friendly
#890 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug
Dominant language
Lean
Stars
129
Forks
67
Avg merge
1d 15h
Merged PRs (30d)
16

Description

In the Type Classes chapter we can read "Lean does not allow case analysis of types" and "polymorphic functions implement operations that are uniform for any choice of type argument":
https://github.com/leanprover/reference-manual/blob/5d2a1e3c97acc754de5b9751efd6d13ba6666530/Manual/Classes.lean#L42

In the Axioms chapter we can read "parametricity is [...] not compatible with Lean's standard axioms":
https://github.com/leanprover/reference-manual/blob/5d2a1e3c97acc754de5b9751efd6d13ba6666530/Manual/Axioms.lean#L74

It also has an example that does case analysis on whether a type is Nat
https://github.com/leanprover/reference-manual/blob/5d2a1e3c97acc754de5b9751efd6d13ba6666530/Manual/Axioms.lean#L90

I believe the intent in the Type Classes chapter was for computable functions only (in particular functions that don't use the axiom of choice). But the text as currently written is a bit misleading (since it doesn't mention computability or the absence of axiom of choice explicitly).

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by comparing the cited passages in Manual/Classes.lean and Manual/Axioms.lean, especially the lines linked in the issue. Clarify the Type Classes discussion so its claim about uniform polymorphic functions is scoped consistently with the axiom-of-choice and computability context, then verify that the two chapters no longer appear contradictory.

Written by the indexing model from the issue text.

Assessment

Domain
documentation
Issue type
Documentation
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
72/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.