Implement lawful Functor and Traversable instances (if possible)

[chshersh]

No description provided.

[0xd34df00d]

Looks like it's only possible for those monoids that "make sense" for any contained value type. I can only think of First, Last and maybe some obscure stuff like Data.Functor.Contravariant's Equivalence. Do you think it still makes sense given this?

[chshersh]

@0xd34df00d What do you mean by saying monoids that "makes sense"? The idea was to traverse a treap once, mapping all elements and recalculating all monoidal values in nodes. So it's possible to implement a function like this without any problems:

fmap :: Measured n b => (a -> b) -> Treap m a -> Treap n b

However, due to the Functor nature, it's not possible to implement such fmap inside the instance declaration. It maybe possible with -XQuantifiedConstraints, and I've tried to implement this instance, but my knowledge of QuantifiedConstraints is limited. So I would love to hear more expert thoughts on how to do this correctly and whether this can be done or not 🙂

https://github.com/chshersh/treap/blob/d7af2076c7ba3d31fb6b7694bdc0449144e104f9/src/Treap/Pure.hs#L100-L109

And if it cannot be done, let's implement at least fmat with the type signature above and sane name.