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

Export Set intersections and Intersection #1038

Closed
meooow25 opened this issue Sep 13, 2024 · 1 comment · Fixed by #1040
Closed

Export Set intersections and Intersection #1038

meooow25 opened this issue Sep 13, 2024 · 1 comment · Fixed by #1040

Comments

@meooow25
Copy link
Contributor

#756 added these two definitions

-- | The intersection of a series of sets. Intersections are performed left-to-right.
intersections :: Ord a => NonEmpty (Set a) -> Set a
intersections (s0 :| ss) = List.foldr go id ss s0
where
go s r acc
| null acc = empty
| otherwise = r (intersection acc s)
-- | Sets form a 'Semigroup' under 'intersection'.
newtype Intersection a = Intersection { getIntersection :: Set a }
deriving (Show, Eq, Ord)
instance (Ord a) => Semigroup (Intersection a) where
(Intersection a) <> (Intersection b) = Intersection $ intersection a b
stimes = stimesIdempotent

but they were never exported from Data.Set.

We should export them, but there is an opportunity for improvement today. base-4.18 got Foldable1, so we could change intersections to be (Ord a, Foldable1 f) => f (Set a) -> Set a.

And whatever we do for Set we should also do for IntSet.

@meooow25
Copy link
Contributor Author

meooow25 commented Sep 14, 2024

Ah, there's something to be considered about IntSet. Unlike Set, we can have a monoid because mempty is well defined here (fromList [minBound..maxBound]). But this set cannot be constructed in practice because it is too large. So I think we should not have the instance, though technically it could be defined correctly.

If we end up implementing #999 it will be practical to construct this set and we can revise this decision.

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

Successfully merging a pull request may close this issue.

1 participant