Ord for partially ordered sets

[Reid Barton]

On Fri, Apr 24, 2015 at 10:23 AM, Ivan Lazar Miljenovic <
ivan.miljenovic at gmail.com> wrote:

> On 25 April 2015 at 00:01, Henning Thielemann
> <lemming at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20150504/a97d8b16/attachment-0001.html>