search

kowainik / treap

:leaves: :deciduous_tree: :fallen_leaf: Efficient implementation of the implicit treap data structure
Mozilla Public License 2.0
63 stars 1 forks source link

Implement lawful `Functor` and `Traversable` instances (if possible) #22

Open chshersh opened 5 years ago

0xd34df00d commented 4 years ago

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 commented 4 years ago

@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 :slightly_smiling_face:

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.