[Haskell-cafe] Faster set intersections?
siddu.druid at gmail.com
Sun Dec 9 18:31:56 UTC 2018
I don't understand, how does
(a -> Bool) -> a
model a set?
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  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.
>  http://hackage.haskell.org/package/infinite-search
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> 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...
More information about the Haskell-Cafe