Data structure to manage collection of sets with efficient lookup, intersection?
New to Haskell, with a mental block about how to represent this situation efficiently: I have an unknown function f which is defined on subsets of some universal set (say integers 1...N). I know the values of f for some subsets, and using those can infer values on other subsets. So what I need is a way to manage a collection of subsets s_i (and the associated values f(s_i)) so that I can efficiently (a) check whether a subset s is already 'known' in my collection, and (b) find all subsets t in the collection that intersect s. In a "traditional" language, I'd likely create a dictionary with keys s_i containing the f(s_i) as values, along with a separate dictionary keyed on the elements of the universal set (1...N) in which each entry is a list of all s_i containing the given element of the universal set. Together they let me check, given a subset s, whether I know f(s), and also get the list of all known subsets intersecting s (by the union of the lists of sets containing each element of s). I can't quite wrap my head around how to do this efficiently in Haskell, maybe because of the way the above is duplicating information about the subsets across two different data structures? Any thoughts? Thanks, Patrick ________________________________________________________________________ DISCLAIMER: This e-mail is intended only for the addressee named above. As this e-mail may contain confidential or privileged information, if you are not the named addressee, you are not authorised to retain, read, copy or disseminate this message or any part of it. If you received this email in error, please notify the sender and delete the message from your computer.
"Patrick Surry" <Patrick.Surry@portraitsoftware.com> wrote:
New to Haskell, with a mental block about how to represent this situation efficiently:
I have an unknown function f which is defined on subsets of some universal set (say integers 1...N). I know the values of f for some subsets, and using those can infer values on other subsets.
So what I need is a way to manage a collection of subsets s_i (and the associated values f(s_i)) so that I can efficiently (a) check whether a subset s is already 'known' in my collection, and (b) find all subsets t in the collection that intersect s.
In a "traditional" language, I'd likely create a dictionary with keys s_i containing the f(s_i) as values, along with a separate dictionary keyed on the elements of the universal set (1...N) in which each entry is a list of all s_i containing the given element of the universal set. Together they let me check, given a subset s, whether I know f(s), and also get the list of all known subsets intersecting s (by the union of the lists of sets containing each element of s).
I can't quite wrap my head around how to do this efficiently in Haskell, maybe because of the way the above is duplicating information about the subsets across two different data structures?
Any thoughts?
Look at Data.Map and start coding instead of prematurely optimising. Haskell allows you to express this purely algorithmic, there's no need for data structures in the traditional sense: You can build in memoisation afterwards. http://haskell.org/ghc/docs/latest/html/libraries/containers/Data-Map.html -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited.
Patrick.Surry:
In a "traditional" language, I'd likely create a dictionary with keys s_i containing the f(s_i) as values, along with a separate dictionary keyed on
The usual dictionary type to use is Data.Map, you might also try Data.IntMap if your keys are word-sized integers.
the elements of the universal set (1...N) in which each entry is a list of all s_i containing the given element of the universal set. Together they
So that sounds like another Map.
let me check, given a subset s, whether I know f(s), and also get the list of all known subsets intersecting s (by the union of the lists of sets containing each element of s).
I can't quite wrap my head around how to do this efficiently in Haskell, maybe because of the way the above is duplicating information about the subsets across two different data structures?
Seems like you'd do it much the same way -- with a pair of dictionaries (in this case, purely functional finite maps, defined in: http://haskell.org/ghc/docs/latest/html/libraries/containers/Data-Map.html An example, Prelude Data.Map> let m = fromList (zip [1..10] (repeat "haskell")) :: Map Int String Prelude Data.Map> Data.Map.lookup 4 m "haskell" Cheers, Don
participants (3)
-
Achim Schneider -
Don Stewart -
Patrick Surry