[Haskell-cafe] lexicographic order

Simeon Mattes simeon.mattes at gmail.com
Sun Mar 30 16:45:54 EDT 2008

Hello everyone,

I would like to ask something that I found in the ebook "a Gentle
Introduction to Haskell".

data Tree a = Leaf a | Branch (Tree a) (Tree a)
instance  (Ord a) => Ord (Tree a)  where
    (Leaf _)     <= (Branch _)      =  True
    (Leaf x)     <= (Leaf y)        =  x <= y
    (Branch _)   <= (Leaf _)        =  False
    (Branch l r) <= (Branch l' r')  =  l == l' && r <= r' || l <= l'

The latter specifies a lexicographic order: Constructors are ordered by the
order of their appearance the data declaration, and the arguments of a
constructor are compared from left to right.

Although I have tried to make sense what lexicographic order means I haven't
figured out. Maybe an example with a simple application of this would be
helpful. To be honest I can't understand what the symbol <= really means.


View this message in context: http://www.nabble.com/lexicographic-order-tp16381434p16381434.html
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

More information about the Haskell-Cafe mailing list