"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?
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.