Data.Graph transitive closure

[Andrew Butterfield]

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 <johannes.waldmann at htwk-leipzig.de> 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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

--------------------------------------------------------------------
Andrew Butterfield     Tel: +353-1-896-2517     Fax: +353-1-677-2204
Lero at 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/
--------------------------------------------------------------------