It would be useful to have complexity information in the documentation for functions

[expipiplus1]

It would be handy for the documentation to confirm the expected time and space complexity of the functions in fgl. Given that all the functions operate over instances of Graph (and friends) rather than concrete types these bounds might have to be given in terms of the number of calls the Graph's member functions, or given in terms of an idealized implementation of Graph.

This is particularly useful given the relative complexity of determining this information in Haskell.

[ivan-m]

The problem with this is that it depends on what the underlying instances have for complexities. But yes, this would be a good thing to have.

[ivan-m]

So I've started doing so here; what do you think?

I'm not sure how feasible this will be though, as a lot of it starts to become "this is whatever the complexity of that function in the type class is" style :s

[expipiplus1]

It might be worthwhile giving the complexity for IntMap and PatriciaTree, does anyone use any other types?

[ivan-m]

Not that I know of. They also have similar complexities (IIRC, apart from noNodes, the only difference is that PatriciaTree has better constants albeit with a possible pathological case that shouldn't occur in actual usage).

I'm wanting to make a release today or tomorrow with the QuickCheck version bump, so I may delay finishing this until a better model presents itself.

[ntc2]

Giving the complexity in terms of IntMap or PatriciaTree, like @expipiplus1 suggests, seems like a simple solution that cover most users.