Re: [Haskell-cafe] Faster set intersections?

Am 09.12.2018 um 19:47 schrieb 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? I think so. The empty set is then represented by the function that returns Nothing even on (const True). Indeed, with Maybe on the outside the intersection function requires the Eq constraint on the base type: We have member :: Eq a => a -> ((a -> Bool) -> a) -> Bool member x find = x == (find (x==))

Then the intersection of find and find' can be implemented using \p -> find (\x -> p x && member x find') But I fail to see how having Maybe on the inside remedies this situation. Furthermore, on Eq types these sets are not so interesting, for the following reason. One can write a function Eq a => ((a -> Bool) -> a) -> [a] that enumerates the elements of the set. Because we have universal quantification, this list can not be infinite. Which makes sense, topologically: These so-called searchable sets are topologically compact, and the Eq constraint means the space is discrete. Compact subsets of a discrete space are finite. Olaf

On Sun, Dec 9, 2018, 1:41 PM MigMit

...

On 9 Dec 2018, at 19:36, Brandon Allbery wrote:

Naïvely, a set implemented as a predicate determining membership?

On Sun, Dec 9, 2018 at 1:32 PM Siddharth Bhat wrote: I don't understand, how does

(a -> Bool) -> a

model a set?

Thanks Siddharth

On Sun, 9 Dec, 2018, 22:08 Olaf Klinke, 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@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.