CODEWITHSUNDEEP
haskell
DoubleOseven
DoubleOseven

Reputation: 271

Haskell guard expression explanation

comp shows if two words are lexicographically equal or smaller 

import Data.Char
class MyComp a where
   comp :: a -> a -> Bool
instance MyComp Char where
   comp num1 num2 = (ord num1) <= (ord num2)       -- ord :: Char -> Int


instance MyComp a => MyComp [a] where
   comp [] _ = True
   comp _ [] = False
   comp (x:xs) (y:ys)
    | comp x y && comp y x = comp xs ys
    | comp x y = True
    | otherwise = False

The code above is little cryptic to me. Can someone explain to me what is going on in the guards? Why are they checking to see if both comp x y and comp y x are true. Shouldn't just 

| comp x y = comp xs ys
| otherwise = False

do the trick?

Upvotes: 0

Views: 146

Answers (2)

Daniel Martin
Daniel Martin

Reputation: 23548

comp is basically an extended less-than-or-equals function.

The code you have a question about is about extending a definition of less-than-or-equal from type a to type [a]. It does this with the traditional definition of lexicographic ordering.

Now, as there is no formal relationship between MyComp and Eq you can't really ask x == y - instead, the only way to ask if x and y are equal according to comp is to do the double test you ask about there.

That double test is to handle this case:

"abcd" `comp` "aacd"

Now, this should be false because "aacd" should sort before "abcd". But to do that you need to check beyond the first letter. That's what the code you're asking about is doing - it's checking the second (and subsequent) letters in the case where the initial letters are equal.

But you don't always check the subsequent letters! What about the case:

comp "abcd" "baaa"

Obviously, this should be true even though comp 'a' 'b' is true and comp "bcd" "aaa" is false.

Upvotes: 2

redneb
redneb

Reputation: 23870

It appears from the definition of MyComp that the intention is that comp x y is equivalent to x <= y. Now, the definition instance MyComp a => MyComp [a] means that if the less-than-or-equal-to relation is defined for values of type a, then it is also defined for values of type [a], presumably using the lexicographical order.

The way the lexicographical order works is that if you are comparing two lists, you first compare the first element of the first list with the first element of the second list. If they differ, then you use the result of that comparison as the result of the comparison of the two lists. If on the other hand they are equal, then you look at the second element from both lists and so on. That's what the above code is trying to do: comp x y && comp y x is like saying that x <= y && y <= x, which is equivalent to saying that x is equal to y. If the happens. then according to the lexicographical order, you have to discard those two elements and look at the remainder of the two lists.

Upvotes: 1

Related Questions