[Haskell-cafe] Faster set intersections?

[Brandon Allbery]

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