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

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