[Haskell-cafe] Data structure to manage collection of sets with
efficient lookup, intersection?
Don Stewart
dons at galois.com
Mon May 5 17:22:37 EDT 2008
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
More information about the Haskell-Cafe
mailing list