Ok, here is a new "IntMap" module that might improve the performance of "lookup". Please, let's first test it before adding the changes to the real distribution. I have: 1) removed calls to "natFromInt" and "intFromNat". Supposedly, they should expand to nothing but who knows... 2) I have commented out the guard that tests if the integer is in the tree at all. When a key is present, lookup will be faster -- if the key is not present, lookup might be slower. Simon, I would be interested to see how it performs with and without the comment (2) (line 269). If performance is better without the comment, it means that ghc is spending time doing intFromNat/natFromInt which means that we might improve matters by storing Nat's instead of Int's in the IntMap. (I don't know if such tweaking is worth the trouble though.) All the best, Daan.