Problem with a Functor instance over the keys in Map from Data.Map

I'm trying to write Eric Kidd's and Sigfpe's code for a probability monad using Data.Map as a backend but I'm stuck with a Functor instance.

I have a data type which is a probability table:

newtype Prob f a = Prob {table :: Map a f}

which at each value for the variable of type a associate is probability, which is of type Floating f => f. The instance should be given by:

instance (Floating f) => Functor (Prob f) where 
   fmap f (Prob tab) = Prob (mapKeysWith (+) f tab)

but mapKeysWith have typ开发者_StackOverflow社区e (Ord k2) => Map k1 a -> (a -> a -> a) -> (k1 -> k2) -> Map k2 a. I have no way of enforcing the Ord constraint in the instance, and so I have a type error.

Is there a simple way out of this?

Nothing simple, I'm afraid; it's a well known problem with Functor (and Monad). As usual, Oleg has a solution (for Set, but Map is solved the same way) if you can rewrite to use a replacement Functor instance. (See also liboleg on Hackage.)