[Haskell-cafe] Data structure to manage collection of sets with efficient lookup, intersection?

[Don Stewart]

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