[Haskell-cafe] Ord for partially ordered sets

Ivan Lazar Miljenovic ivan.miljenovic at gmail.com
Fri Apr 24 14:23:42 UTC 2015

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.

Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com

More information about the Haskell-Cafe mailing list