Support for proving the equations of match expressions with value patterns.
The match compiler generates a tree of tests dite (x = v) (Eq.ndrec_symm m) e for value
patterns, where x is a variable and v a value. When proving the equation of an alternative with
overlapping patterns, the goal tree = rhs contains a hypothesis such as
x = "a" → y = 0 → False, or ∀ ys, some (x, y) = some ("a", ys) → False, for each previous
alternative.
splitDiteTree proves such a goal by traversing the tree. It does not use general purpose
tactics because their cost at each test is proportional to the number of hypotheses, and there is
one test and one hypothesis for each alternative.
- At a test
x = v, it keeps the hypothesish : x = vin thethenbranch, and replacesxwithvonly in the right-hand siderhs. The other hypotheses still mentionx. - It indexes the hypotheses of the form
... → Falseusing the testsx = voccurring in them. At a testx = v, the index returns the hypotheses whose tests have all been performed. Only these hypotheses are rewritten using the kept equalities, and used to close thethenbranch. - At a leaf that is not a test, e.g., a
casesOnapplication, it substitutes the kept equalities, and returns the goal.
Given a goal tree = rhs where tree is a tree of tests dite (x = v) (Eq.ndrec_symm m) e,
traverses the tree and closes the branches that are refuted by a hypothesis of the form
... → False, or where both sides are definitionally equal. Returns the goals for the remaining
branches. Throws an exception if the goal is not of this form.
Equations
- One or more equations did not get rendered due to their size.