Haskell multiple functors

I'm making a fibonacci heap implementation in Haskell, and I'm not sure exactly what the clean way to do it.

For example, I want to order the nodes. So I can do something like:

instance Ord (FibNode e) where
  f1 `compare` f2 = (key f1) `compare` (key f2)

This would be more easily done if I made FibNode a mona开发者_Go百科d. But other times I want to fold across the node's siblings, or fold across their children etc. So defining a functor where f x = f $ key x won't work all the time.

Apart from defining my own fmapKey, fmapSibs, fmapKids... is there a way to do this?

You can't make a type constructor an instance of Functor in more than one way. But you can make various newtype wrappers around your type that each has its own Functor instance. But that's not really any more convenient than defining your own fmap functions.

The (Fibonacci) heap is an inherently impure, destructively-updated data structure with specific asymptotic runtime guarantees for various operations on it. I would be surprised if you can maintain these guarantees with a straightforward translation to a pure version. My suggestion would be to to make it an impure data structure using something like the ST or IO arrays. This would make for a much more direct implementation of the classic algorithms.