Using associated data types to create unpacked data structures

[Simon Marlow]

On 11/08/2010 17:03, Johan Tibell wrote:
> Inspired by the generic maps example at
>
> http://www.haskell.org/haskellwiki/GHC/Indexed_types
>
> I tried to use associated data types to create a generic finite map that
> unpacks both the key and value into the leaf data constructor.

What you're trying to do is have the compiler generate a whole module 
for you, including a datatype specialised to certain type paramters, and 
operations over that type.  Just defining a few of the operations isn't 
enough: they need to be inlined everywhere, essentially you need to 
recompile Data.Map for each instance.

So I agree it would be nice if this happened automatically, behind the 
scenes, by virtue of just mentioning "Map Int Double" (though it would 
still have to be a typeclass of course, so that you can write 
polymorphic functions over Maps).  Automatic specialisation of this kind 
can be done by JIT runtimes (e.g. the .NET CLR), because there the code 
generation and caching of instances can be put under control of the 
runtime.  Here we would have to do it in the compiler, and the 
difficulty is that the compiler needs to support separate compilation.

Rather than try to solve this problem in one go, I would go for a 
low-tech approach for now: write a TH library to generate the code, and 
ask the user to declare the versions they need.  To make a particular 
version, the user would say something like

   module MapIntDouble (module MapIntDouble) where
   import TibbeMagicMapGenerator
   make_me_a_map ...

there's no type class of course, so you can't write functions that work 
over all specialised Maps.  But this at least lets you generate 
optimised maps for only a little boilerplate, and get the performance 
boost you were after.

Cheers,
	Simon