The goal is similar, but I'm attempting to automatically infer the appropriate map type for any algebraic datatype -- and while I'm at it, the TrieMap package aims to include all the methods Data.Map offers.

Perhaps you want to read about the type-indexed tries in "Generic Haskell: Applications": http://www.cs.uu.nl/~johanj/publications/ghpractice.pdf

Sean