<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Sat, Dec 8, 2018 at 7:46 PM Jeffrey Brown <<a href="mailto:jeffbrown.the@gmail.com">jeffbrown.the@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">The following expressions both cause GHCI to hang:<div><span style="font-family:monospace"><span style="color:rgb(0,0,0)">
</span><br>> S.intersection (S.fromList [1,2]) (S.fromList [1..])
<br>fromList ^CInterrupted.
<br>> S.intersection (S.fromList [1..]) (S.fromList [1,2])
<br>fromList ^CInterrupted.
<br>> <br>
<br></span><div>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)?</div></div></div></blockquote><div><br></div><div>Taking the intersection of already-constructed, finite sets is very fast if one of them is small (should be O(n lg m) where n is the size of the smaller set and m the size of the larger one).  However, Data.Set doesn't handle infinite sets as it tries to construct balanced trees and is strict in the keys.  Even fromAscList won't help you here.  To represent infinite (or bigger than you actually want to construct) sets you'll likely need to roll your own custom representation, and I suspect it will in general need to either have limitations on the key space or worse asymptotic performance.</div><div><br></div><div>That said, you can often get the behavior you're looking for by representing big sets by a membership predicate and using filter.  Here's an (untested) example of the right sort of thing:</div><div><br></div><div>data MySet k = Pred (k -> Bool) | Concrete (S.Set k)</div><div><br></div><div>intersection (Pred a) (Pred b) = Pred (\k -> a k && b k)</div><div>intersection (Concrete a) (Pred b) = Concrete (S.filter b a)</div><div>intersection (Pred a) (Concrete b) = Concrete (S.filter a b)</div><div>intersection (Concrete a) (Concrete b) = Concrete (S.intersection a b)</div><div><br></div><div>Note that a concrete set "concretizes" anything it touches.  Don't take unions of these sets, though, it'll just be a mess.</div><div><br></div><div>-Jan-Willem Maessen</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><br></div>-- <br><div dir="ltr" class="m_-128266526926237527gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>Jeff Brown | Jeffrey Benjamin Brown</div><div dir="ltr"><a href="https://msu.edu/~brown202/" style="font-size:12.8px" target="_blank">Website</a>   |   <a href="https://www.facebook.com/mejeff.younotjeff" style="font-size:12.8px" target="_blank">Facebook</a>   |   <a href="https://www.linkedin.com/in/jeffreybenjaminbrown" style="font-size:12.8px" target="_blank">LinkedIn</a><span style="font-size:12.8px">(spammy, so I often miss messages here)   </span><span style="font-size:12.8px">|</span><span style="font-size:12.8px">   </span><a href="https://github.com/jeffreybenjaminbrown" style="font-size:12.8px" target="_blank">Github</a><span style="font-size:12.8px">   </span></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div></div>