Re: Data.Graph transitive closure

Dear Johannes, Carter, David, libraries, As a formal methodist who likes and uses functional languages a lot, I looked at doing this in a "principled" way a long time ago. The idea was to formally specify an abstract graph datatype and various graph operations (create, query, modify, transitive closure, etc, etc...) and then show correctness of of simple but possibly inefficient implementations. Then the plan was to develop efficient operations, including use of appropriate graph representation types, and show formally that they were refinements of the inefficient ones. It rapidly became *very* clear that the best/only? way to do something efficiently was to decide which operations were important, and specialise for those. Woe betide you if you left out an operator that later would be important, because its efficient implementation could well force you to do complete re-design. Basically, it is not feasible to design a large/general-purpose graph library that does everything efficiently. I then got distracted by something else..... Regards, Andrew

On 21 Jun 2019, at 19:48, Johannes Waldmann wrote:

On 21.06.19 20:44, Carter Schonwald wrote:

...

... it seems doubtful that there'll ever be a one true [graph] library

Yes. My point was that Data.Graph isn't a "graph library" (it was never meant to be) - it's a "DFS/SCC library".

- J. _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

-------------------------------------------------------------------- Andrew Butterfield Tel: +353-1-896-2517 Fax: +353-1-677-2204 Lero@TCD, Head of Foundations & Methods Research Group School of Computer Science and Statistics, Room G.39, O'Reilly Institute, Trinity College, University of Dublin http://www.scss.tcd.ie/Andrew.Butterfield/ --------------------------------------------------------------------