[Haskell-beginners] Ord [] instance

[Daniel Fischer]

Am Samstag 31 Oktober 2009 20:39:57 schrieb Keith Sheppard:
> the compare function for lists seems to be work like (leaving off
>
> class details):
> > compare [] [] = EQ
> > compare [] _ = LT
> > compare _ [] = GT
> > compare (x:xt) (y:yt) = case x `compare` y of
> >     EQ -> xt `compare` yt
> >    _ -> x `compare` y
>
> I poked around to see if I could find where this was defined in the
> spec or if it was an implementation specific thing (I need to be able
> to rely on this definition across implementations).

You can rely on lexicographic ordering for lists.

Haskell Report, section 10.1 ( http://haskell.org/onlinereport/derived.html#derived-
appendix ):

10.1  Derived instances of Eq and Ord
The class methods automatically introduced by derived instances of Eq and Ord are (==), 
(/=), compare, (<), (<=), (>), (>=), max, and min. The latter seven operators are defined 
so as to compare their arguments lexicographically with respect to the constructor set 
given, with earlier constructors in the datatype declaration counting as smaller than 
later ones.

> I found this text in the report:
>
> -- Lists
>
>
> data  [a]  =  [] | a : [a]  deriving (Eq, Ord)
> -- Not legal Haskell; for illustration only
>
> Is this basically saying the same thing as my compare definition?

Yes, see above.

>
> Thanks
> Keith