[Haskell-cafe] Faster set intersections?

[Siddharth Bhat]

According to this construction, enumeration will need some SAT enumeration
like process, where you search with a new predicate barring all previous
candidates?

On Mon, 10 Dec, 2018, 08:50 Doug McIlroy, <doug at cs.dartmouth.edu> wrote:

> > The following expressions both cause GHCI to hang:
> >
> > S.intersection (S.fromList [1,2]) (S.fromList [1..])
> > S.intersection (S.fromList [1..]) (S.fromList [1,2])
> >
> > Is there a smarter way to take the intersection of sets when at least one
> > of them is small (but I don't know which one that is)?
>
> "Small" is not enough. If all you know is that the lists
> represent sets of integers, then
>
>    S.intersection (S.fromList [-1,-2]) (S.fromList [1..])
>
> must diverge. A sufficient condition for success in such examples
> is that the sets come from a well-ordered domain and are presented
> in order. Then it's easy to write a merge-like algorithm.
> Both sets can be infinite; every finite prefix of the intersection
> will eventually appear.
>
> (Note that the integers are not well-ordered, though the positive
> integers are.)
>
> Doug
> _______________________________________________
> 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/bb8d977d/attachment.html>