[Haskell-cafe] Faster set intersections?

[Tom Ellis]

That would be `a -> Bool`.

On Sun, Dec 09, 2018 at 01:36:06PM -0500, Brandon Allbery wrote:
> Naïvely, a set implemented as a predicate determining membership?
> 
> On Sun, Dec 9, 2018 at 1:32 PM Siddharth Bhat <siddu.druid at gmail.com> wrote:
> 
> > I don't understand, how does
> >
> > (a -> Bool) -> a
> >
> > model a set?
> >
> > Thanks
> > Siddharth
> >
> > On Sun, 9 Dec, 2018, 22:08 Olaf Klinke, <olf at aatal-apotheke.de> wrote:
> >
> >> > Note that a concrete set "concretizes" anything it touches.  Don't take
> >> > unions of these sets, though, it'll just be a mess.
> >> >
> >> >
> >> > Won't a union just be the same as intersection but using || instead of
> >> && ?
> >> >
> >> >
> >> > -Jan-Willem Maessen
> >>
> >> Unions of predicates and concrete sets are easy, thanks to Set.member:
> >>
> >> union (Pred p) (Concrete s) = Pred (\k -> p k || member k s)
> >>
> >> What you can not do, of course, is enumerate and fold these sets.
> >> There is a set type [1] which supports a litte bit more:
> >>
> >> Set a = Maybe ((a -> Bool) -> a)
> >>
> >> It has unions, intersections and a Monad instance and can represent
> >> infinite sets. If the base type has an Ord instance, the set can be
> >> enumerated. If the base type has an Eq instance, so has (Set a). Some
> >> functions usually implemented using Foldable are also possible, e.g.
> >> minimum and maximum.
> >> Caveat: Performance can be poor, depending on how the function inside the
> >> set was defined.
> >>
> >> Cheers,
> >> Olaf
> >>
> >> [1] http://hackage.haskell.org/package/infinite-search
> >> _______________________________________________
> >> Haskell-Cafe mailing list
> >> To (un)subscribe, modify options or view archives go to:
> >> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> >> Only members subscribed via the mailman list are allowed to post.
> >
> > --
> > Sending this from my phone, please excuse any typos!
> > _______________________________________________
> > Haskell-Cafe mailing list
> > To (un)subscribe, modify options or view archives go to:
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> > Only members subscribed via the mailman list are allowed to post.
> 
> 
> 
> -- 
> brandon s allbery kf8nh
> allbery.b at gmail.com

> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.