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)

Haskell Data.List.Class and syntax

1 Answers