[Haskell-cafe] Faster set intersections?

[Siddharth Bhat]

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!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20181210/f4118a34/attachment.html>