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