leanprover / leanprover/lean4

`ac_rfl` unable to solve a goal using commutativity

Open
#7,330 0 comments 2 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug P-low
Dominant language
Lean
Stars
9.2k
Forks
990
Avg merge
1d 17h
Merged PRs (30d)
175

Description

Prerequisites

Please put an X between the brackets as you perform the following steps:

Description

The ac_rfl tactic cannot solve a seemingly obvious goal by using commutativity provided by the Std.Commutative instance in the hypothesis.

Steps to Reproduce
theorem Option.merge_comm {α : Type} (f : α → α → α) [h : Std.Commutative f] (a b : Option α) :
  Option.merge f a b = Option.merge f b a := by
  cases a <;> cases b <;> simp [Option.merge]
  ac_rfl

Expected behavior: ac_rfl solves the goal

Actual behavior: ac_rfl fails, reporting tactic 'rfl' failed, equality lhs ... is not definitionally equal to rhs ...

Versions
Lean 4.19.0-nightly-2025-03-04
Target: x86_64-unknown-linux-gnu
Additional Information

ac_rfl works as intended on the associativity proof goal below.

theorem Option.merge_assoc {α : Type} (f : α → α → α) [Std.Associative f] (a b c : Option α) :
  Option.merge f (Option.merge f a b) c = Option.merge f a (Option.merge f b c) := by
  cases a <;> cases b <;> cases c <;> simp [Option.merge]
  ac_rfl
Impact

Add 👍 to issues you consider important. If others are impacted by this issue, please ask them to add 👍 to it.

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 with the minimal Option.merge_comm reproduction and inspect the ac_rfl tactic behavior when commutativity comes from Std.Commutative. Compare it with the provided Option.merge_assoc case, then run the reproduction against the reported Lean nightly version. Done means ac_rfl solves the commutative goal while preserving the associativity behavior.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.