Inconsistent order of arguments to BEq in list operations
Nobody has claimed this yet.
- Dominant language
- Lean
- Stars
- 9.2k
- Forks
- 990
- Avg merge
- 1d 17h
- Merged PRs (30d)
- 175
Description
List / Array / Vector operations currently do not agree on the order when calling beq:
-
elem,contains,replace,lookup(and indirectlyinsert) use thea == l[i]convention (the parameter to the operation is on the left, and the tested list element is on the right) despite documentation claiming the opposite -
erase,countand[fin]idxOf[?]use thel[i] == aconvention (the tested list element is on the left, and the parameter to the operation is on the right)
This inconsistency results in undesirable behavior when operations are mixed. Consider isPerm, which checks if two lists have the same elements excluding order. One might expect isPerm to never return true when the two lists don't even agree on size; unfortunately that does not happen in the general case, because the cons branch
| a :: l₁, l₂ => l₂.contains a && l₁.isPerm (l₂.erase a)
mixes operations of both conventions, so it's possible for .contains a to claim a match while the subsequent .erase a fails to find it.
Would it be acceptable to align all operations on the same convention, or is it not worth it the effort/breakage just for avoiding a PartialEquivBEq constraint? A friend offered to ask @digama0 and IIUC the feedback was positive, but as the guidelines ask to first create an issue I thought it would be nice to get more feedback :)
Also @digama0 you mentioned there have been recent patches towards consistency in == order but I wasn't able to find them, could you point me to them if you have them at hand?
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by comparing the BEq argument order in the listed List, Array, and Vector operations, especially contains, erase, count, and idxOf variants. Then trace isPerm, including its contains/erase combination, to understand the inconsistent behavior. Done means the operations follow one documented convention and mixed operations no longer produce contradictory matches.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Refactor
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100