[Haskell-cafe] Faster set intersections?

[Olaf Klinke]

> Am 09.12.2018 um 19:31 schrieb Siddharth Bhat <siddu.druid at gmail.com>:
> 
> I don't understand, how does 
> 
> (a -> Bool) -> a
> 
> model a set?
MigMit was right. When I learned about this, I thought is was black magic. Suppose 
find :: (a -> Bool) -> a
This function 'find' models a hypothetical non-empty set S. The specification is that for every predicate 
p :: a -> Bool
that terminates on every element of S (this condition is important!), find p will be a member of S that satisfies p, if there is such a member, and any member of S otherwise. Since find is specified to always return a member of S, the set S is guaranteed to be non-empty. You can select some element from S by calling 'find' on (const True). 

For example, the singleton x is defined as the constant function
\p -> x
The doubleton {x,y} is defined as 
\p -> if p x then x else y
Binary union is defined as 
union find find' = \p -> if p (find p) then find p else find' p
Existential quantification over S:
exists p = p (find p)
Universal quantification over S:
forall p = not (exists (not.p))

In order to represent the empty set as well, I stuck in the Maybe, so that Nothing represents the empty set and (Just find) represents a non-empty set. 

Olaf
> 
> 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!