[Haskell-cafe] Faster set intersections?

[David Feuer]

That does seem to be what the source code says. The code only handles
non-empty sets, but I *believe* the Maybe-wrapped version can handle
intersections, albeit inefficiently. Can a version that looks like (a ->
Bool) -> Maybe a work?

On Sun, Dec 9, 2018, 1:41 PM MigMit <migmit at gmail.com wrote:

> My guess — by finding a member that satisfies a predicate, if it's at all
> possible, and any member if the predicate is const False. It's actually
> pretty awesome.
>
> > On 9 Dec 2018, at 19:36, Brandon Allbery <allbery.b at gmail.com> 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.
>
> _______________________________________________
> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20181209/a086db16/attachment.html>