Unable to instantiate class due to missing instance

Question

I have this haskell code. In that I have created two data types, then I want to to create a new class Mord that can do comparing functions with Mlist types.

import Data.List

data Mlist a = Mlist [a]

data Mordering = MLT deriving (Eq, Show)

s = Mlist [1, 2, 3]
t = Mlist [1, 4, 2, 3]

class Mord a where 
    mcompare :: a -> a -> Mordering


instance Mord a => Mord (Mlist a) where
    mcompare (Mlist xs) (Mlist ys) = MLT

But if I try mcompare s t I get

<interactive>:1:1:
    No instance for (Mord Integer)
      arising from a use of `mcompare'
    Possible fix: add an instance declaration for (Mord Integer)
    In the expression: mcompare s t
    In an equation for `it': it = mcompare s t

Does anyone see the problem?

EDIT:

Here is my new code:

import Data.List

data Mlist a = Mlist [a]

data Mordering = MEQ | MIN deriving (Eq, Show)

s = Mlist [1, 2, 3]
t = Mlist [1, 4, 2, 3]

class Mord a where 
    mcompare :: a -> a -> Mordering

instance Mord (Mlist a) where
    mcompare (Mlist xs) (Mlist ys)
           | length xs == length ys && null (xs \\ ys) = MEQ
           | otherwise = MIN

But the error I get now is:

    No instance for (Eq a)
      arising from a use of `\\'
    In the first argument of `null', namely `(xs \\ ys)'
    In the second argument of `(&&)', namely `null (xs \\ ys)'
    In the expression: length xs == length ys && null (xs \\ ys)
Failed, modules loaded: none.

Answer 1

Haskell reads this:

instance Mord a => Mord (Mlist a) where
    mcompare (Mlist xs) (Mlist ys) = MLT

as meaning "for every a for which I have an instance of Mord, I also have an Mord instance of Mlist a. But, if I don't have an Mord instance for a, then I also don't have an Mord instance for Mlist a. Sorry, but let's hang out again sometime!"

The Mord a part of the instance declaration is known as a context; you can read more about this in A Gentle Introduction to Haskell.

Instance contexts are useful with type constructors, such as [] and Mlist from your code. For example, we can look at the standard Eq class and [a]'s instance for it:

instance (Eq a) => Eq [a] where
    []     == []     = True
    (x:xs) == (y:ys) = x == y && xs == ys
    _xs    == _ys    = False

What does this instance mean? Two empty lists are equal; two non-empty lists are equal if their heads are equal and their tails are equal; any two other non-empty lists are unequal; an empty and non-empty list are unequal.

I've bolded part of the previous paragraph because it helps answer the question "why are instance contexts useful?" Well, in the list example, part of the definition of list equality comes from the structure of lists, but the other part is based on the equality of its elements. In other words, you can't compare lists for equality unless you can compare its elements for equality.

Functions are the classic example of values that can't be meaningfully compared for equality. So how could we check if lists of functions are equal?

ghci> (+1) == (*2)
<interactive>:6:6:
    No instance for (Eq (a0 -> a0))
      arising from a use of `=='
    Possible fix: add an instance declaration for (Eq (a0 -> a0))
    In the expression: (+ 1) == (* 2)
    In an equation for `it': it = (+ 1) == (* 2)

ghci> [(+4)] == [\x -> 2 * x / 3]
<interactive>:8:8:
    No instance for (Eq (a0 -> a0))
      arising from a use of `=='
    Possible fix: add an instance declaration for (Eq (a0 -> a0))
    In the expression: [(+ 4)] == [\ x -> 2 * x / 3]
    In an equation for `it': it = [(+ 4)] == [\ x -> 2 * x / 3]

So to get your code working, you can either remove the instance context as it's not being made use of, or you need to provide an appropriate underlying instance, i.e.:

instance Mord Int where
    mcompare ... = ...

s :: Mlist Int
s = Mlist [1, 2, 3]
t :: Mlist Int
t = Mlist [1, 4, 2, 3]

Answer 2

instance Mord a => Mord (Mlist a) where

Here you said that Mlist a is an instance of Mord if and only if a is an instance of Mord. Integer is not an instance of Mord, so Mlist Integer is also not an instance of Mord. If you define an instance Mord Integer, your code will work.

In response to your edit: Your new code doesn't work because \\ only works on lists of values that can be compared for equality (i.e. values of types that are instances of the Eq typeclass). Since you don't have an Eq constraint on your instance, you're saying that it should work for all types, but since \\ doesn't work with all types, you can't do that. Adding an Eq constraints to your instance (i.e. instance (Eq a) => Mord (Mlist a) ...) will fix your issue.

Answer 3

I'm going to zoom in on one particular point, other answers are already covering the immediate problem.

Suppose you managed to get everything working with the help you got so far, and you've started up GHCi and loaded your code. Let's try it out:

ghci> mcompare s t
MLT
ghci> mcompare t s
MLT

Hmm. that doesn't seem very useful to me! What's going on?

If we look at what mcompare actually does when given two Mlists - to be precise, at this instance declaration:

instance Mord a => Mord (Mlist a) where
    mcompare (Mlist xs) (Mlist ys) = MLT

we can see that there's no comparison going on at all; whatever xs and ys are, mcompare just returns MLT. In a way that's logical, because the Mordering data type has only got one value:

data Mordering = MLT deriving (Eq, Show)

But to represent the result of a comparing operation, you're generally going to need 3 possible results: the first argument is less than, equal to, or greater than the second argument. You could argue there's also an 'uncomparable' option, but let's not get into that there!

So you want your Mordering data type to contain those three comparison results, you can do that by adding some more constructors (this was what I was talking about in the comments to sepp2k's answer), as in:

data Mordering = LessThan 
               | EqualTo 
               | GreaterThan 
                   deriving (Eq,Show)

(I'm guessing you meant something like data Mordering = MLT | MEQ | MGT deriving (Eq, Show) maybe?)

This opens up a new bag of problems, and I'll give you some hints to help you on your way.

---

First, we want mcompare 3 4 to be LessThan, mcompare 5 5 to be EqualTo and mcompare 7 6 to be GreaterThan, because 3 is less than 4 (and so on). To achieve this, you need an instance of Mord for Integer:

instance Mord Integer where
    mcompare x y
        | x <  y = ...
        | x == y = ...
        | x >  y = ...

Filling in the blanks shouldn't be too difficult, I hope!

The second part is slightly trickier: given that we can compare values of type a, how do we compare values of type Mlist a? In other words, how should the instance Mord a => Mord (Mlist a) declaration be written? The result of mcompare (Mlist xs) (Mlist ys) will depend on whether xs is empty, whether ys is empty, and if both are not empty, on how the first element of xs and ys compare and how the rest of the elements compare.

I'll leave that for you to figure out; don't hesitate to ask a new question showing how far you got and where you are stuck!