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

[Achim Schneider]

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