-
Notifications
You must be signed in to change notification settings - Fork 16
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
Clarify laws of TestEquality #21
Comments
https://hackage.haskell.org/package/base-4.14.0.0/docs/Data-Type-Equality.html#t:TestEquality says "Conditionally prove the equality of An interesting question is whether we allow individual instances to return false negatives (= operate under stricter rules). I think it is fine: maybe types are equal, but |
Yes the first part implies the weakest, and only
hints at the strongest. Nothing hints the middle. The false negatives question is good too, thanks. |
The key monad is a good example of something that instance TestEquality (Key s)
instance Monad (KeyM s)
newKey :: KeyM s (Key s a)
runKeyM :: (forall s . KeyM s a) -> a Key is realistically an Int, and KeyM state linear in an Int. I can imagine uses for weakest equality like closed operations where you don't mind if the values differ but require the same type. In fact you can recover the utility of strongest equality from weakest anyway: -- really should be Eq (f a) | Eq (f b) =>
testEqual :: (TestEquality f, Eq (f a)) => f a -> f b -> Maybe (a :~: b)
testEqual a b = mfilter (\Refl -> a == b) (testEquality a b) I guess you could have usual equivalence relation laws for TestEquality and TestCoercion, where the two arguments are related if they return Just Refl or Just Coercion. |
I assume this is a rare case, where we need CLC approval for documentation, because it clarifies semantics unexpressable otherwise. Since no one raised a voice in favor of options other than the weakest notion, could someone please to raise an MR for CLC to vote on? |
I am going to try to get some of the people from https://github.com/GaloisInc/parameterized-utils to chime in here, as the "weakest" direction is a bit contrary form their current documented laws, though not in a fundamental way. (They are doing the exact same thing as the classes from https://hackage.haskell.org/package/some) |
Just wanted to add, if you exclude false negatives for the type parameter, you arrive at decidable equality for the type parameter. This implies returning Either (¬ eq) eq rather than Maybe eq, as in |
For our use cases in parameterized-utils, it's important that we have the middle Eq-like equality. If |
@robdockins OK just wanted to make sure one of you knew, so thank for chiming in. As I wrote in GaloisInc/parameterized-utils#62, I recommend using https://hackage.haskell.org/package/some for |
Indeed, I think if what is desired from |
In the absense of clarification in I'd say that the wording "This class contains types where you can learn the equality of two types from information contained in terms" prohibits returning false negative answers: One could raise a CLC proposal asking to change the semantics of |
It is unclear what `TestEquality` is for. There are 3 possible choices. Assuming ```haskell data Tag a where TagInt1 :: Tag Int TagInt2 :: Tag Int ``` `Just Refl` merely means the type params are equal, the values being compared might not be ```haskell instance TestEquality where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt1 TagInt2 = Just Refl testEquality TagInt2 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl ``` `Just Refl` means the type params are equal, and the values are equal according to `Eq`. ```haskell instance TestEquality where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl testEquality _ _ = Nothing ``` - `Just Refl` means the type params are equal, and the values are equal, and the class assume if the type params are equal the values must also be equal. In other words, the type is a singleton type when the type parameter is a closed term. ```haskell -- instance TestEquality -- invalid instance because two variants for `Int` ``` ------ The discussion in haskell/core-libraries-committee#21 on this topic is veering towards the weakest option so that is what is implementing here, so that is what I am implementing. The committee will vote on this change.
It is unclear what `TestEquality` is for. There are 3 possible choices. Assuming ```haskell data Tag a where TagInt1 :: Tag Int TagInt2 :: Tag Int ``` ## Weakest -- type param equality only `Just Refl` merely means the type params are equal, the values being compared might not be ```haskell instance TestEquality where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt1 TagInt2 = Just Refl testEquality TagInt2 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl ``` ## Middle -- Like `Eq` `Just Refl` means the type params are equal, and the values are equal according to `Eq`. ```haskell instance TestEquality where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl testEquality _ _ = Nothing ``` ## Strongest -- unique value concrete type `Just Refl` means the type params are equal, and the values are equal, and the class assume if the type params are equal the values must also be equal. In other words, the type is a singleton type when the type parameter is a closed term. ```haskell -- instance TestEquality -- invalid instance because two variants for `Int` ``` ------ The discussion in haskell/core-libraries-committee#21 on this topic is veering towards the weakest option so that is what is implementing here, so that is what I am implementing. The committee will vote on this change.
I made https://gitlab.haskell.org/ghc/ghc/-/merge_requests/7333 |
Dear CLC members, let's have a vote on https://gitlab.haskell.org/ghc/ghc/-/merge_requests/7333 +1 from me. |
I know I'm coming really late, but I think either:
|
|
What is a good witness for inequality in Haskell? I do think "lawless" is too harsh plenty of classes (e.g. |
Just to chime in, I don't think I understand the "lawless" objection either. The class is already lawless in the sense that it doesn't have any stated laws (hence this discussion). I think probably everyone assumes the operation given should define some equivalence relation on the values in the family So, do we want to require that values be considered equivalent iff their types are equal? This seems unnecessarily strong to me, but is a reasonable stance. I agree with @Ericson2314 that negative type equality information isn't useful; in my mind this is a good reason to reject this requirement. I don't think that additional law enables any interesting programming patterns. Then, we end up in the case that I think is most useful, which is that |
Hmm I thought original purpose was Honestly, It might just be best to remove this from base. It's unclear what it's for or why it's there. This thing seems too half-baked to deserve to be in base.
Conversely, a class for singletons or |
So like data Decision a = No (a -> Void) | Yes a
class DecidableEquality f where
decideEquality :: f a -> f b -> Decision (a :~: b) Getting type families to reduce is currently mostly impossible, but special cases could be handled like this: type family a === b where
a === a = True
_ === _ = False
data EqualityRes a b where
YesEqual :: EqualityRes a a
NotEqual :: (a === b) ~ 'False => EqualityRes a b
class Blahblahblah f where
yeppers :: f a -> f b -> EqualityRes a b |
Pulling out of base would allow us to experiment which of @treeowl's options are better for the full decidability use-case. I hope with things like https://gitlab.haskell.org/ghc/ghc/-/merge_requests/3868 working with negated coercersions might start to get more ergonomic / useful, too. |
I don't think you need to pull If the final judgment is that |
@robdockins one doesn't need to strictly speaking, yes, but the weakest option just isn't that useful IMO. it's a type class whose only purpose is to be subtypeclassed to better serve the two uses we've identified, one of which wants a generalized While I personally want to see more super-fine-grained class hierarchies, Haskell itself isn't currently isn't set up very well for it, nor has |
The current Haddocks for TestEquality seem reasonably clear that the intention of the class is to learn equalities of types from information contained in terms, and not to compare terms themselves for equality, though it also specifies that it should usually only have instances which are singletons, which makes that question a moot point. Based on the documentation I'd support either the weakest interpretation, or discarding the class. We have GEq/GCompare for term equality that also learns about type equality as it goes. I wouldn't be wholly opposed to putting those in base, but I also wouldn't rush to do it, since that just makes working on them harder. I'm not sure I've ever seen this TestEquality class put to use. If we were to just remove it, how much would break? |
Well, it would break a bunch of stuff at Galois. This class is used throughout our program analysis suite of tools, both for singleton-style type representatives, and for broader uses, as I've argued for above. If I would implore the core library committee to make API-breaking changes to |
I dont know when the policy for removing things from base is, but I would assume it would be deprecated first, then removed, to give people time and advanced notice. @robdockins I also would volunteer to send PRs to your open source repos like |
47 packages according to https://hackage-search.serokell.io/?q=TestEquality I do not quite follow the discussion above. Are there specific non-breaking suggestions to incorporate in https://gitlab.haskell.org/ghc/ghc/-/merge_requests/7333 ? |
The discussion was an alternative of (deprecating and eventually) removing it altogether. The search is nice, I suppose we can see what use-case is more common. |
Yeah, in the case that people are getting use out of it, I'm fine with
clarifying its meaning, but not with removal. GEq seems like an almost
totally separate concept to me, that just happens to overlap in the case of
singletons.
…On Fri., Jan. 14, 2022, 19:09 John Ericson, ***@***.***> wrote:
The discussion as an alternative of (deprecating and eventually) removing
it altogether.
The search is nice, I suppose we can see what use-case is more common.
—
Reply to this email directly, view it on GitHub
<#21 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ABVVE3H3MRE3A4Y4IGVFXQ3UWC3MVANCNFSM5JFM5YHQ>
.
Triage notifications on the go with GitHub Mobile for iOS
<https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675>
or Android
<https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.
You are receiving this because you were mentioned.Message ID:
***@***.***>
|
Looks like we just need some more votes on the PR as written, then? |
I'm in favour of clarifying the semantics to the weakest definition as described in the MR. +1 |
+1 to the weakest semantics described in the MR |
+1 to clarifying the documentation without changing the meaning as it stands. |
With 4 votes out of 6 in favor, the proposal https://gitlab.haskell.org/ghc/ghc/-/merge_requests/7333 is approved. Thanks everyone. |
It is unclear what `TestEquality` is for. There are 3 possible choices. Assuming ```haskell data Tag a where TagInt1 :: Tag Int TagInt2 :: Tag Int ``` Weakest -- type param equality semi-decidable --------------------------------------------- `Just Refl` merely means the type params are equal, the values being compared might not be. `Nothing` means the type params may or may not be not equal. ```haskell instance TestEquality Tag where testEquality TagInt1 TagInt1 = Nothing -- oopsie is allowed testEquality TagInt1 TagInt2 = Just Refl testEquality TagInt2 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl ``` This option is better demonstrated with a different type: ```haskell data Tag' a where TagInt1 :: Tag Int TagInt2 :: Tag a ``` ```haskell instance TestEquality Tag' where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt1 TagInt2 = Nothing -- can't be sure testEquality TagInt2 TagInt1 = Nothing -- can't be sure testEquality TagInt2 TagInt2 = Nothing -- can't be sure ``` Weaker -- type param equality decidable --------------------------------------- `Just Refl` merely means the type params are equal, the values being compared might not be. `Nothing` means the type params are not equal. ```haskell instance TestEquality Tag where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt1 TagInt2 = Just Refl testEquality TagInt2 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl ``` Strong -- Like `Eq` ------------------- `Just Refl` means the type params are equal, and the values are equal according to `Eq`. ```haskell instance TestEquality Tag where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl testEquality _ _ = Nothing ``` Strongest -- unique value concrete type --------------------------------------- `Just Refl` means the type params are equal, and the values are equal, and the class assume if the type params are equal the values must also be equal. In other words, the type is a singleton type when the type parameter is a closed term. ```haskell -- instance TestEquality -- invalid instance because two variants for `Int` ``` ------ The discussion in haskell/core-libraries-committee#21 on this topic is veering towards the weakest option so that is what is implementing here, so that is what I am implementing. The committee will vote on this change.
It is unclear what `TestEquality` is for. There are 3 possible choices. Assuming ```haskell data Tag a where TagInt1 :: Tag Int TagInt2 :: Tag Int ``` Weakest -- type param equality semi-decidable --------------------------------------------- `Just Refl` merely means the type params are equal, the values being compared might not be. `Nothing` means the type params may or may not be not equal. ```haskell instance TestEquality Tag where testEquality TagInt1 TagInt1 = Nothing -- oopsie is allowed testEquality TagInt1 TagInt2 = Just Refl testEquality TagInt2 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl ``` This option is better demonstrated with a different type: ```haskell data Tag' a where TagInt1 :: Tag Int TagInt2 :: Tag a ``` ```haskell instance TestEquality Tag' where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt1 TagInt2 = Nothing -- can't be sure testEquality TagInt2 TagInt1 = Nothing -- can't be sure testEquality TagInt2 TagInt2 = Nothing -- can't be sure ``` Weaker -- type param equality decidable --------------------------------------- `Just Refl` merely means the type params are equal, the values being compared might not be. `Nothing` means the type params are not equal. ```haskell instance TestEquality Tag where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt1 TagInt2 = Just Refl testEquality TagInt2 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl ``` Strong -- Like `Eq` ------------------- `Just Refl` means the type params are equal, and the values are equal according to `Eq`. ```haskell instance TestEquality Tag where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl testEquality _ _ = Nothing ``` Strongest -- unique value concrete type --------------------------------------- `Just Refl` means the type params are equal, and the values are equal, and the class assume if the type params are equal the values must also be equal. In other words, the type is a singleton type when the type parameter is a closed term. ```haskell -- instance TestEquality -- invalid instance because two variants for `Int` ``` ------ The discussion in haskell/core-libraries-committee#21 has decided on the "Weaker" option (confusingly formerly called the "Weakest" option). So that is what is implemented.
It is unclear what `TestEquality` is for. There are 3 possible choices. Assuming ```haskell data Tag a where TagInt1 :: Tag Int TagInt2 :: Tag Int ``` Weakest -- type param equality semi-decidable --------------------------------------------- `Just Refl` merely means the type params are equal, the values being compared might not be. `Nothing` means the type params may or may not be not equal. ```haskell instance TestEquality Tag where testEquality TagInt1 TagInt1 = Nothing -- oopsie is allowed testEquality TagInt1 TagInt2 = Just Refl testEquality TagInt2 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl ``` This option is better demonstrated with a different type: ```haskell data Tag' a where TagInt1 :: Tag Int TagInt2 :: Tag a ``` ```haskell instance TestEquality Tag' where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt1 TagInt2 = Nothing -- can't be sure testEquality TagInt2 TagInt1 = Nothing -- can't be sure testEquality TagInt2 TagInt2 = Nothing -- can't be sure ``` Weaker -- type param equality decidable --------------------------------------- `Just Refl` merely means the type params are equal, the values being compared might not be. `Nothing` means the type params are not equal. ```haskell instance TestEquality Tag where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt1 TagInt2 = Just Refl testEquality TagInt2 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl ``` Strong -- Like `Eq` ------------------- `Just Refl` means the type params are equal, and the values are equal according to `Eq`. ```haskell instance TestEquality Tag where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl testEquality _ _ = Nothing ``` Strongest -- unique value concrete type --------------------------------------- `Just Refl` means the type params are equal, and the values are equal, and the class assume if the type params are equal the values must also be equal. In other words, the type is a singleton type when the type parameter is a closed term. ```haskell -- instance TestEquality -- invalid instance because two variants for `Int` ``` ------ The discussion in haskell/core-libraries-committee#21 has decided on the "Weaker" option (confusingly formerly called the "Weakest" option). So that is what is implemented.
It is unclear what `TestEquality` is for. There are 3 possible choices. Assuming ```haskell data Tag a where TagInt1 :: Tag Int TagInt2 :: Tag Int ``` Weakest -- type param equality semi-decidable --------------------------------------------- `Just Refl` merely means the type params are equal, the values being compared might not be. `Nothing` means the type params may or may not be not equal. ```haskell instance TestEquality Tag where testEquality TagInt1 TagInt1 = Nothing -- oopsie is allowed testEquality TagInt1 TagInt2 = Just Refl testEquality TagInt2 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl ``` This option is better demonstrated with a different type: ```haskell data Tag' a where TagInt1 :: Tag Int TagInt2 :: Tag a ``` ```haskell instance TestEquality Tag' where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt1 TagInt2 = Nothing -- can't be sure testEquality TagInt2 TagInt1 = Nothing -- can't be sure testEquality TagInt2 TagInt2 = Nothing -- can't be sure ``` Weaker -- type param equality decidable --------------------------------------- `Just Refl` merely means the type params are equal, the values being compared might not be. `Nothing` means the type params are not equal. ```haskell instance TestEquality Tag where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt1 TagInt2 = Just Refl testEquality TagInt2 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl ``` Strong -- Like `Eq` ------------------- `Just Refl` means the type params are equal, and the values are equal according to `Eq`. ```haskell instance TestEquality Tag where testEquality TagInt1 TagInt1 = Just Refl testEquality TagInt2 TagInt2 = Just Refl testEquality _ _ = Nothing ``` Strongest -- unique value concrete type --------------------------------------- `Just Refl` means the type params are equal, and the values are equal, and the class assume if the type params are equal the values must also be equal. In other words, the type is a singleton type when the type parameter is a closed term. ```haskell -- instance TestEquality -- invalid instance because two variants for `Int` ``` ------ The discussion in haskell/core-libraries-committee#21 has decided on the "Weaker" option (confusingly formerly called the "Weakest" option). So that is what is implemented.
I'm trying to summarise the state of this proposal as part of my volunteering effort to track the progress of all
Please, let me know if you find any mistakes 🙂 |
(See obsidiansystems/dependent-sum#31 and GaloisInc/parameterized-utils#63 for some background.)
It is unclear what
TestEquality
is for. There are 3 possible choices.Assuming
Weakest -- type param equality semi-decidable
Just Refl
merely means the type params are equal, the values being compared might not be.Nothing
means the type params may or may not be not equal.This option is better demonstrated with a different type:
Weaker -- type param equality decidable
Just Refl
merely means the type params are equal, the values being compared might not be.Nothing
means the type params are not equal.Strong -- Like
Eq
Just Refl
means the type params are equal, and the values are equal according toEq
.Strongest -- unique value concrete type
Just Refl
means the type params are equal, and the values are equal, and the class assume if the type params are equal the values must also be equal. In other words, the type is a singleton type when the type parameter is a closed term.-- instance TestEquality -- invalid instance because two variants for `Int`
I don't care that much which choice is made, as long as a choice is made!
The text was updated successfully, but these errors were encountered: