search

haskell / fgl

A Functional Graph Library for Haskell
http://hackage.haskell.org/package/fgl
Other
185 stars 54 forks source link

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

Open expipiplus1 opened 8 years ago

expipiplus1 commented 8 years ago

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

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

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

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

ivan-m commented 8 years ago

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

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