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

Set union not necessarily commutative #84

Open
rightfold opened this issue Mar 13, 2019 · 2 comments
Open

Set union not necessarily commutative #84

rightfold opened this issue Mar 13, 2019 · 2 comments

Comments

@rightfold
Copy link

rightfold commented Mar 13, 2019

JoinSemiLattice requires that join is commutative, but this is not necessarily true for the instance JoinSemiLattice (Set a) where join = union.

Consider this valid total order:

data X = X Int String
instance Eq X where (X a _) (X b _) = a == b
instance Ord X where (X a _) (X b _) = a `compare` b

Now with:

a = fromList [X 1 "A"]
b = fromList [X 1 "B"]

The following do not give the same result:

union a b
union b a
@phadej
Copy link
Collaborator

phadej commented Mar 13, 2019

λ Data.Set> data X = X Int String deriving (Show)
λ Data.Set> instance Eq X where (X a _) == (X b _) = a == b
λ Data.Set> instance Ord X where compare (X a _) (X b _) = a `compare` b
λ Data.Set> a = fromList [X 1 "A"]
λ Data.Set> b = fromList [X 1 "B"]
λ Data.Set> union a b
fromList [X 1 "A"]
λ Data.Set> union b a
fromList [X 1 "B"]
λ Data.Set> union a b == union b a
True

I don't see a problem. Your Eq / Ord says they are EQual.

@rightfold
Copy link
Author

rightfold commented Mar 14, 2019

They are equivalent according to the equivalence relation Eq (Set X), but they are not the same value. One is fromList [X 1 "A"] whereas the other one is fromList [X 1 "B"].

If you want the semilattice laws to hold with respect to Eq, rather than extensional equality, how would you describe them for the instance JoinSemiLattice (a -> b)?

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