On Fri, Apr 24, 2015 at 10:23 AM, Ivan Lazar Miljenovic <ivan.miljenovic@gmail.com> wrote:
On 25 April 2015 at 00:01, Henning Thielemann
<lemming@henning-thielemann.de> wrote:
>
> On Fri, 24 Apr 2015, Ivan Lazar Miljenovic wrote:
>
>> Specifically, I have a pull request for fgl [1] to add Ord instances for
>> the graph types (based upon the Ord instances for Data.Map and Data.IntMap,
>> which I believe are themselves partially ordered), and I'm torn as to the
>> soundness of adding these instances.
>
>
> In an application we needed to do some combinatorics of graphs and thus
> needed Set Graph.
>
> Nonetheless, I think that graph0 < graph1 should be a type error. We can
> still have a set of Graphs using a newtype.

This could work; the possible problem would be one of efficiency: if
it's done directly on the graph datatypes they can use the underlying
(ordered) data structure; going purely by the Graph API, there's no
guarantees of ordering and thus it would be needed to call sort, even
though in practice it's redundant.

Not to endorse any particular decision on the topic of the thread, but I'd point out that there is no problem here from a technical point of view. The Graph API can export a function `compareGraphs :: Graph -> Graph -> Ordering` which uses the underlying representation, but not provide an Ord instance which uses it. Then a user of the library can use `compareGraphs` in an Ord instance for a newtype wrapper, or as an argument to functions like `sortBy`.

Regards,
Reid Barton