Using associated data types to create unpacked data structures
marlowsd at gmail.com
Thu Aug 12 05:28:29 EDT 2010
On 11/08/2010 17:03, Johan Tibell wrote:
> Inspired by the generic maps example at
> 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
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.
More information about the Glasgow-haskell-users