Avoiding O(n^2) instances when using associated data types to unpack values into constructors

Don Stewart dons at galois.com
Tue Jul 6 13:23:03 EDT 2010


johan.tibell:
> Hi,
> 
> I'm trying to create a data type for maps where both keys and values are
> unpacked into the data type constructors (see code at the end of this email). I
> achieve this using an associated data type of two arguments (`Map` in the code
> below). The problem I have is that this definition requires O(n^2) instances. I
> use a CPP macro to make it easier to create these instances but it doesn't
> address the real problem that the number of instances grows quadratically.

I've a TH macro in the adaptive-containers package you might use as
well.

> Is there a better way to have GHC unpack the keys and values into the data
> constructors?

Not that I know of, other than reusing some of the primitive types where
possible (Int/Word).

-- Don


More information about the Glasgow-haskell-users mailing list