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
http://IvanMiljenovic.wordpress.com


More information about the Libraries mailing list