"Patrick Surry" <[EMAIL PROTECTED]> wrote: > 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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe