Creating a new Ord instance for Lists

Question

This is my first attempt at creating a custom instance of a class such as Ord.

I've defined a new data structure to represent a list:

data List a = Empty | Cons a (List a)
    deriving (Show, Eq)

Now I want to define a new instance of Ord for List such that List a <= List b implies "the sum of the elements in List a is less than or equal to the sum of the elements in List b"

first of all, is it necessary to define a new "sum" function since the sum defined in Prelude wont work with the new List data type? then, how do I define the new instance of Ord for List?

thanks

Answer 1

First of all, this won't work exactly like the normal list instance. The normal instance only depends on the items of the list being orderable themselves; your proposal depends on their being numbers (e.g. in the Num class) and so is more narrow.

It is necessary to define a new sum function. Happily it's very easy to write sum as a simple recursive function. (Coincidentally, you can call your function sum', which is pronounced as "sum prime" and by convention means it's a function very similar to sum.)

Additionally, the instance would have to depend on the Num class as well as the Ord class.

Once you have a new sum function, you can define an instance something like this:

instance (Ord n, Num n) => Ord (List n) where compare = ... 
  -- The definition uses sum'

This instance statement can be read as saying that for all types n, if n is in Ord and Num, List n is in Ord where comparisons work as follows. The syntax is very similar to math where => is implication. Hopefully this makes remembering the syntax easier.

You have to give a reasonable definition of compare. For reference, compare a b works as follows: if a < b it returns LT, if a = b it returns EQ and if a > b it returns GT.

This is an easy function to implement, so I'll leave it as an exercise to the reader. (I've always wanted to say that :P).