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

Fix equality definition to take bag semantics into account #62

Open
10 tasks
jeromesimeon opened this issue Aug 26, 2017 · 0 comments
Open
10 tasks

Fix equality definition to take bag semantics into account #62

jeromesimeon opened this issue Aug 26, 2017 · 0 comments

Comments

@jeromesimeon
Copy link
Member

jeromesimeon commented Aug 26, 2017

Leibnitz equality (eq) equates two collections only if they have the same order.
Since we assume collections are bags, we should be using bag equality (equivalence modulo permutation).

Note that we avoided this issue for records by enforcing that well-typed records are sorted.
In this case, sorting would be more painful, since we would need a <= relation on all data (not just on strings).

  • Add the right equivalence relation for data, and show that it is an equivalence relation and that it is decidable.
  • Show that it is a morphism for the data_type relation.
  • Show that it is a morphism for the evaluation relations.
    • CAMP
    • NRA*
    • NNRC*
  • Change our untyped and typed equivalence definitions
    • CAMP
    • NRA*
    • NNRC*

In addition, operators (e.g., ADistinct), should be reviewed to check that they rely on the proper equality relation).

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

No branches or pull requests

1 participant