Haskell Data.List.Class and syntax

Question

I am trying to read the source code for the Haskell package Data.List.Class. (List-0.4.2). But I am stuck with some of the syntax.

Right at the beginning, it reads:

data ListItem l a =
    Nil |
    Cons { headL :: a, tailL :: l a }

I am not familiar with the syntax of the 3rd line. I guess that this last line is equivalent to Cons a (l a) ??. But I am not really sure. I noticed that the header of the file says: {-# LANGUAGE FlexibleContexts, TypeFamilies #-}.

Then as I go on, there is a strange use of the type statement: type ItemM l :: * -> *, which I couldn't understand.

Data.List.Class
-- | A class for list types. Every list has an underlying monad.
class (MonadPlus l, Monad (ItemM l)) => List l where
    type ItemM l :: * -> *
    runList :: l a -> ItemM l (ListItem l a)
    joinL :: ItemM l (l a) -> l a
    cons :: a -> l a -> l a
    cons = mplus . return

Can anyone help explain what these mean? I have a perfect understanding of Data.List, but this type class thing is not really clear to me. Also I searched about wiki's, examples, and/or tutorials for using Data.List.{Class,Tree}, but there does not seem to be any, except the comments that come with the code. Any pointers here?

Thanks.

-- update -- The first answer (@Chris) helped me understand the Kind signature and the Record Syntax, which is really helpful. However, I still cannot make sense out of that piece of code overall in terms of how it captures/defines the behavior of a List and what value it adds to the familiar Data.List definitions. Here are some further details, where there are only two instance statements. Also the Identity term comes from import Data.Functor.Identity (Identity(..)). Can you please help explain what this is type class do to capture the characteristics of a list as we normally know it? Again, I searched it online but there is really no documentation for Data.List.Class except the code itself. Anyone knows?

Also, is there another example use of the type statement in the typeclass constraint similar to what's in this example? I searched learnyouahaskell.com/ (@Landei) but couldn't find such an example. I am assuming that the usage of type here is similar to how you would use typedef's in C++ templates to define 'functions on types', right?

Thanks again.

instance List [] where
    type ItemM [] = Identity
    runList [] = Identity Nil
    runList (x:xs) = Identity $ Cons x xs
    joinL = runIdentity
    cons = (:)

instance Functor m => Functor (ListItem m) where
    fmap _ Nil = Nil
    fmap func (Cons x xs) = Cons (func x) (fmap func xs)

Answer 1

Record Syntax

This

data ListItem l a = Nil | Cons { headL :: a, tailL :: l a }

is called record syntax. You're correct when you guess that the structure is the same as if you'd typed

data ListItem l a = Nil | Cons a (l a)

However, you also get the two accessor functions:

headL :: ListItem l a -> a
headL (Cons a _) = a

tailL :: ListItem l a -> l a
tailL (Cons _ as) = as

Record syntax is syntactic sugar - here it saves you around 4 lines of code. You can pattern match in the normal way, as in the code directly above this paragraph, or you can use the record syntax in the pattern match:

safeHeadL :: ListItem l a -> Maybe a
safeHeadL Nil                = Nothing
safeHeadL (Cons {headL = a}) = Just a

Again, this is desugared into standard pattern matching.

Kind Signatures

This

class (MonadPlus l, Monad (ItemM l)) => List l where
  type ItemM l :: * -> *
  runList :: l a -> ItemM l (ListItem l a)
  joinL   :: ItemM l (l a) -> l a

  cons :: a -> l a -> l a
  cons = mplus . return

is a type family declaration. The line

  type ItemM l :: * -> *

is a kind signature. When we say something has kind *, we mean that it's a base type, like Int or Float. To say that something has kind * -> * means that it is a type constructor, i.e. it takes a type and returns another type.

The Maybe type constructor has this kind signature:

Maybe :: * -> *

Remember that Maybe on its own isn't a type. It has to be given a type, and then it returns a type. Give it Int and you get Maybe Int. Give it Double and you get Maybe Double.

The type constructor ItemM l takes a type parameter (of kind *) and returns something of kind *. Note that since l is of kind *, you have

ItemM :: * -> * -> *

i.e. ItemM takes two types, and returns a type (equivalently, it takes one type and returns a unary type constructor).

By including the type declaration in the class, you impose the constraint that in all instances of the class, the l in ItemM l has to match up with the l in List l. It's impossible to create an instance of the class where these don't match up.