User-defined List instance

Question

This is supposed to be really simple, but I cannot seem to get around it.

Suppose I have my own List class, declaring head and tail in its interface. List is supposed to be what you expect, that is a collection of homogeneous items. Then, I want to create a data type implementing the List interface.

The following code is what I came up with, but it does not work: how would you fix it?

class List l where                                                             
    head :: l -> a  -- ERROR! How do I tell: given a list, return an element?                                                      
    tail :: l -> l                                                             

data ConsList a = Nil | Cons a (ConsList a)                                    

instance List (ConsList Int) where                                             
    head Nil = error "Empty List"                                              
    head (Cons h _) = h                                                        
    tail Nil = error "Empty List"                                              
    tail (Cons _ t) = t                       

Thanks in advance!

Answer 1

Rather than defining List a type class, define it as a constructor class:

class List l where
    head :: l a -> a
    tail :: l a -> l a                                        

data ConsList a = Nil | Cons a (ConsList a)

instance List ConsList where
    head Nil = error "Empty List"
    head (Cons h _) = h
    tail Nil = error "Empty List"
    tail (Cons _ t) = t

Alternatively, fix the element type (note: for your type ConsList, this requires flexible instances):

{-# LANGUAGE FlexibleInstances #-}

class List l where
    head :: l -> Int
    tail :: l -> l

data ConsList a = Nil | Cons a (ConsList a)

instance List (ConsList Int) where
    head Nil = error "Empty List"
    head (Cons h _) = h
    tail Nil = error "Empty List"
    tail (Cons _ t) = t

Finally, with type families you can do even more fancy stuff, but it really depends on your specific scenario if you should go that far (probably not):

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE TypeFamilies      #-}

class List l where
    type Elt l
    head :: l -> Elt l
    tail :: l -> l

data ConsList a = Nil | Cons a (ConsList a)

instance List (ConsList Int) where
    type Elt (ConsList Int) = Int

    head Nil = error "Empty List"
    head (Cons h _) = h

    tail Nil = error "Empty List"
    tail (Cons _ t) = t