Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Feature: basic pattern matching for data-types #26

Open
alexkeizer opened this issue Jun 26, 2024 · 0 comments
Open

Feature: basic pattern matching for data-types #26

alexkeizer opened this issue Jun 26, 2024 · 0 comments
Assignees

Comments

@alexkeizer
Copy link
Owner

We can attempt to define a data_def command that has the same syntax as regular def, but allows a rudimentary form of defining recursive functions through pattern matching.

We already have Fix.dest which will unfold an element of type (Fix F) \alpha to an element of F (Fix \alpha).
In the framework, F will be the Base type, which is in turn just an application of the inductively defined Shape type, so we should be able to do normal pattern matching on the result of Fix.dest. Our data_def wrapper could use this trick internally.

The challenge is defining a recursive function; I don't expect Lean to be able to recognize this will terminate in finite time. Thus, our wrapper should come up with a decreasing measure, using the decreasing_by machinery.
Combined, that should let us define recursive functions.

A downside is that well-founded recursion generally has worse def-eqs than structural recursion. I'm not a 100% sure where recursion using MvQPF.Fix.rec fits, but presumably we will want a proper equation compiler at some point. This wrapper is a nice stepping stone towards that, though.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants