On Mon, Dec 8, 2008 at 2:04 AM, Martin Hofmann <span dir="ltr"><<a href="mailto:martin.hofmann@uni-bamberg.de">martin.hofmann@uni-bamberg.de</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I am storing the TH data types 'Exp' and 'Pat' in Maps and Sets. As a<br>
first attempt to quickly get rid of typechecker's complaints I defined<br>
some naive instances of Ord for Exp and Pat.<br>
<br>
Now it took me about a week to realise, that 'instance Ord Pat' causes<br>
ghc to loop. Apparently, there is a reason, why Pat and Exp are not<br>
instances of Ord. What is so bad about it?</blockquote><div><br>Oh, to answer this, my guess is that such an instance is just kind of silly. It is a meaningless, arbitrary ordering, and is brittle to splitting/combining cases. <br>
<br>To put them in sets and maps, go ahead an define an arbitrary ordering however you can, but wrap it in a newtype like this:<br><br>newtype OrdExp = OrdExp Exp<br>instance Ord OrdExp where<br> compare (OrdExp a) (OrdExp b) = compare (show a) (show b)<br>
<br>An orphan instance is one which is defined in a module where neither the class nor the type being instantiated is defined. This newtype wrapping avoids orphan instances, and associates the arbitrary ordering to your own wrapper so if somebody else defined a different arbitrary ordering, they won't conflict.<br>
<br>Orphan instances (almost?) always indicate a nonmodular design decision.<br><br>Luke<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
<br>
If Pat and Exp should not be instances of Ord, maybe a note in the<br>
source code or haddock would be helpful. On the other hand, what would<br>
argue against a lexicographic ordering (apart from the inefficient<br>
implementation of the following one)?<br>
<br>
Following some literate code to reproduce the <<loop>> (or stack<br>
overflow in GHCi), by commenting and uncommenting the appropriate lines:<br>
<br>
<br>
<br>
> {-# OPTIONS_GHC -fglasgow-exts -fth #-}<br>
> module Test where<br>
> import <a href="http://Language.Haskell.TH" target="_blank">Language.Haskell.TH</a><br>
> import Data.Set<br>
<br>
<br>
-------------------<br>
naive Ord<br>
<br>
> instance Ord Exp<br>
<br>
> instance Ord Pat<br>
<br>
-------------------<br>
lexicographic Ord<br>
<br>
instance Ord Exp where<br>
compare l r = compare (show l) (show r)<br>
<br>
instance Ord Pat where<br>
compare l r = compare (show l) (show r)<br>
<br>
-------------------<br>
<br>
<br>
> mkVP s = VarP $ mkName s<br>
> mkVE s = VarE $ mkName s<br>
> rule1 = (,) [mkVP "x_14"] (mkVE "y_14")<br>
> rule2 = (,) [InfixP (mkVP "x1_15") '(:) (mkVP "x_16")] (InfixE (Just (mkVE "y1_15")) (ConE '(:)) (Just (mkVE "ys_16")))<br>
<br>
> stack_overflow = fromList [rule1,rule2]<br>
<br>
<br>
Thanks,<br>
<br>
Martin<br>
<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br>