[Haskell-cafe] Re: Data structure to manage collection of sets with
efficient lookup, intersection?
barsoap at web.de
Mon May 5 09:01:14 EDT 2008
"Patrick Surry" <Patrick.Surry at portraitsoftware.com> 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
(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
More information about the Haskell-Cafe