The following expressions both cause GHCI to hang:
S.intersection (S.fromList [1,2]) (S.fromList [1..]) fromList ^CInterrupted. S.intersection (S.fromList [1..]) (S.fromList [1,2]) fromList ^CInterrupted.
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)? -- Jeff Brown | Jeffrey Benjamin Brown Website <https://msu.edu/~brown202/> | Facebook <https://www.facebook.com/mejeff.younotjeff> | LinkedIn <https://www.linkedin.com/in/jeffreybenjaminbrown>(spammy, so I often miss messages here) | Github <https://github.com/jeffreybenjaminbrown>
I suspect not. Maybe with fromAscList or fromDistinctAscList so it can know the list won't pop a smaller (here, duplicate) value on it, if it's lazy enough (I haven't checked). Lists don't record that they were generated from enumerations. On Sat, Dec 8, 2018 at 7:46 PM Jeffrey Brown <jeffbrown.the@gmail.com> wrote:
The following expressions both cause GHCI to hang:
S.intersection (S.fromList [1,2]) (S.fromList [1..]) fromList ^CInterrupted. S.intersection (S.fromList [1..]) (S.fromList [1,2]) fromList ^CInterrupted.
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)?
-- Jeff Brown | Jeffrey Benjamin Brown Website <https://msu.edu/~brown202/> | Facebook <https://www.facebook.com/mejeff.younotjeff> | LinkedIn <https://www.linkedin.com/in/jeffreybenjaminbrown>(spammy, so I often miss messages here) | Github <https://github.com/jeffreybenjaminbrown>
_______________________________________________ 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
On Sat, Dec 8, 2018 at 7:46 PM Jeffrey Brown <jeffbrown.the@gmail.com> wrote:
The following expressions both cause GHCI to hang:
S.intersection (S.fromList [1,2]) (S.fromList [1..]) fromList ^CInterrupted. S.intersection (S.fromList [1..]) (S.fromList [1,2]) fromList ^CInterrupted.
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)?
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. 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: data MySet k = Pred (k -> Bool) | Concrete (S.Set k) intersection (Pred a) (Pred b) = Pred (\k -> a k && b k) intersection (Concrete a) (Pred b) = Concrete (S.filter b a) intersection (Pred a) (Concrete b) = Concrete (S.filter a b) intersection (Concrete a) (Concrete b) = Concrete (S.intersection a b) Note that a concrete set "concretizes" anything it touches. Don't take unions of these sets, though, it'll just be a mess. -Jan-Willem Maessen
-- Jeff Brown | Jeffrey Benjamin Brown Website <https://msu.edu/~brown202/> | Facebook <https://www.facebook.com/mejeff.younotjeff> | LinkedIn <https://www.linkedin.com/in/jeffreybenjaminbrown>(spammy, so I often miss messages here) | Github <https://github.com/jeffreybenjaminbrown>
_______________________________________________ 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.
On Dec 9, 2018 11:36 AM, "Jan-Willem Maessen" <jmaessen@alum.mit.edu> 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
-- Jeff Brown | Jeffrey Benjamin Brown Website <https://msu.edu/~brown202/> | Facebook <https://www.facebook.com/mejeff.younotjeff> | LinkedIn <https://www.linkedin.com/in/jeffreybenjaminbrown>(spammy, so I often miss messages here) | Github <https://github.com/jeffreybenjaminbrown>
_______________________________________________ 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.
Not like that, no. The Set type is explicitly for *finite* sets only. fromList [1..] is bottom and will run out of memory. You'd need a *very* different implementation to be able to support infinite sets at all, and even then you'd only catch certain special cases. On Sat, Dec 8, 2018, 7:46 PM Jeffrey Brown <jeffbrown.the@gmail.com wrote:
The following expressions both cause GHCI to hang:
S.intersection (S.fromList [1,2]) (S.fromList [1..]) fromList ^CInterrupted. S.intersection (S.fromList [1..]) (S.fromList [1,2]) fromList ^CInterrupted.
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)?
-- Jeff Brown | Jeffrey Benjamin Brown Website <https://msu.edu/~brown202/> | Facebook <https://www.facebook.com/mejeff.younotjeff> | LinkedIn <https://www.linkedin.com/in/jeffreybenjaminbrown>(spammy, so I often miss messages here) | Github <https://github.com/jeffreybenjaminbrown>
_______________________________________________ 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.
Bloom Filters? If some false positives are OK -- Sent from an expensive device which will be obsolete in a few months Casey On Sat, Dec 8, 2018, 4:46 PM Jeffrey Brown <jeffbrown.the@gmail.com wrote:
The following expressions both cause GHCI to hang:
S.intersection (S.fromList [1,2]) (S.fromList [1..]) fromList ^CInterrupted. S.intersection (S.fromList [1..]) (S.fromList [1,2]) fromList ^CInterrupted.
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)?
-- Jeff Brown | Jeffrey Benjamin Brown Website <https://msu.edu/~brown202/> | Facebook <https://www.facebook.com/mejeff.younotjeff> | LinkedIn <https://www.linkedin.com/in/jeffreybenjaminbrown>(spammy, so I often miss messages here) | Github <https://github.com/jeffreybenjaminbrown>
_______________________________________________ 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.
participants (6)
-
Brandon Allbery -
David Feuer -
Ivan Lazar Miljenovic -
Jan-Willem Maessen -
Jeffrey Brown -
KC