Using associated data types to create unpacked data structures

Johan Tibell johan.tibell at
Thu Aug 12 11:56:10 EDT 2010

On Thu, Aug 12, 2010 at 11:28 AM, Simon Marlow <marlowsd at> wrote:

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

To get a better idea of how many specialized maps the user would have to
create under this scheme I ran an analysis of the Chromium codebase [1]. The
Chromium codebase is not small but some companies have codebases which are
several order of magnitudes larger, which makes the results below more of a
lower bound than an upper bound on the number of specialized maps one might
need in a program.

    $ git clone
    Initialized empty Git repository in /tmp/chromium/.git/
    remote: Counting objects: 548595, done.
    remote: Compressing objects: 100% (167063/167063), done.
    remote: Total 548595 (delta 401993), reused 477011 (delta 343049)
    Receiving objects: 100% (548595/548595), 1.02 GiB | 24.44 MiB/s, done.
    Resolving deltas: 100% (401993/401993), done.
    $ cd chromium
    $ find . -name \*.h -o -name \*.cc -exec egrep -o "map<[^,]+, ?[^>]+>"
{} \; | sort -u | wc -l
    $ find . -name \*.h -o -name \*.cc -exec w -l {} \; | awk '{tot=tot+$1}
END {print tot}'

So in a code base of about 80 KLOC there are 220 unique key/value
combinations. While the numbers might not translate exactly to Haskell it
still indicates that the number of modules a user would have to create (and
put somewhere in the source tree) would be quite large.


-------------- next part --------------
An HTML attachment was scrubbed...

More information about the Glasgow-haskell-users mailing list