[Haskell-cafe] lexicographic order

[Bulat Ziganshin]

Hello Simeon,

Monday, March 31, 2008, 12:45:54 AM, you wrote:

> 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.

i'm not sire that i understood your question (are you really never
seen less-or-equal comparison? :), but i can say about lex. order:

if you can compare chars and 'a' < 'b', then *lists* of chars compared
in lexicographic order will be

"aaa" < "aab"
"aab" < "aba"
"baa" < "abb"

and so on - i.e. it finds *left-most* pair of non-equal chars and returns
result based on it comparison

the same principle used for comparison of these trees - any Leaf
smaller than any Branch, if the same constructors are used then their
parameters are compared, from left to right

although the last alternative,

   (Branch l r) <= (Branch l' r')  =  l == l' && r <= r' || l <= l'

seems suspicious to me. isn't it the same as

   (Branch l r) <= (Branch l' r')  =  l <= l'

?




-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com