Alex Rivera | Logout

Haskell Data.List.Class and syntax

Asked 2012-08-02T03:39:29.663
8

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 k

haskell syntax typeclass
Edit
Report

1 Answer

9

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 typ

answered 2012-08-02T04:30:58.463

Your Answer