This would indeed be pretty useful! This comment kinda turned into an essay - sorry!
One way to implement a data structure that would support this sort of extension would be to hide the constructors, and only use them to export a class instance. This class could be pretty simple, like a (forgetful) bijection, or more complicated, providing a lens (implementing this lens efficiently would likely require efficient equality tests, though). The annotation datatype would also implement this typeclass, and could be as simple as "data (FBij a, Default b) => Ann a b = Ann a b". The forgetful bijection would just yield the "a" for pattern matches, and "flip Ann def" for construction.
(yes, forgetful bijection is likely not a technical term)
I've thought about stuff related to this while working on monoidal rope representations of text buffers. Some other ideas I had:
* It'd be convenient to be able to have different annotations to the same structure co-exist, despite not knowing about eachother. Of course, a tuple of the annotations In other words, plugin A doesn't need to know about plugin B, but they both store annotations.
* Data dependencies between annotations - this would allow for expressing what annotations depend on, so that we know when they need to be updated / have been invalidated.
My initial (WIP) solution involved storing a "Map AnnID Dynamic" - not very ideal. I'm not sure if there's a much better solution if it needs to be done at runtime.