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

[Patrick Surry]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080505/496ee6b1/attachment-0001.htm