Lists are the bread and butter of functional programming, and in fact they are extensively used in any programming language. In this article we are going to define our own list in Haskell, and we will use it to solve a couple of interesting problems. Finally we will review the capabilities that Haskell and the standard library provide in terms of lists.
This article is divided in three parts. In the first one we will see what is a list, and how to define it in Haskell. In part two we will explore Pattern Matching and will use it to build functionality using our own list type. In the third part we will see what Haskell and its library has to say about lists (and I guarantee you that we will not use our own list ever again).

What is a list

A list is a sequence container. What? Ok, don't panic. A list is a type of data type that can contain values. For intance a list can contain phone numbers, or the words of a sentence, or the characters of a word. A list is sequential in the sense that the element in a list are organized in sequence, one after the other. If you want to go through the elements on a list, you have to go in sequence from the first to the last.
We use lists in programming for almost anything. You may be building an application to manage a group of students. Most probably those students will be kept in some sort of list. There will be also a list of subjects, a list of teachers, ... you name it.

Show me some code

Ok, let's open ghci and have some fun:

>ghci
GHCi, version 7.6.3 [NG/7.6.3.5]: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude>

In haskell we represent an empty list by a pair of matching square brackets:

Prelude>:t []
[] :: [a]

I have asked Haskell to tell me the type of [], and it has answered that it is a list of some type a. Fair enough, Haskell cannot know what our list is supposed to contained, but it knows that it has to contain things wiht a type, and all of them must have the same type:

Prelude>: [3]
[3] :: Num t => [t]

Now Haskell has a bit more information and can determine that whatever we put in the list must be of type Num. Don't worry about the syntax for the moment. To define a list with several elements simple write them inside the square brackets and separate them by commas:

Prelude>:t [1,2,3]
[1,2,3] :: Num t => [t]

Prelude> [1,2,'a']

<interactive>:10:2:
    No instance for (Num Char) arising from the literal `1'
        Possible fix: add an instance declaration for (Num Char)
        In the expression: 1
            In the expression: [1, 2, 'a']
            In an equation for `it': it = [1, 2, 'a']

Ups! We tried to create a list mixing types, and that is not allowed in Haskell. Haskell tends to be super verbose when reporting errors. This is scaring in the beguining, but quite nice once you understand what those messages are telling you. Let me quickly show you now how to append an element to begining of a list, and how to concatenate 2 lists:

Prelude> 3 : [1,2]
[3,1,2]
Prelude> [1,2] ++ [3,4]
[1,2,3,4]

Very easy indeed!

Defining our own list type

Let's think for a second how we can represent a list. A list has to fundamental states:

Empty
An element followed by a list

Traditionally an empty list in functional languates is called nil, and an element followed by a list is refered to as cons. We can represent the list [1,2,3] as 1 cons ( 2 cons (3 cons nil)), if we use cons as an infix operator, or cons 1 (cons 2 (cons 3 nil)). Haskell provides syntax sugar for cons and nil. Cons is represented as ':', and nil as []. Multiple cons are represented as commas like in [1,2,3].
Let's write some code. Create an empty file and call it Main.hs:

module Main where

-- Algebraic data type. A list is either Empty or
-- is an element followed by a list
data List a = Empty | Cons a (List a)
                      deriving Show

-- Convenience function that returns an empty list
nil :: List a
nil = Empty

-- Append an element to the front of a list
-- Given an element and a list returns a new list
cons :: a -> List a -> List a
cons x = Cons x

Load it in ghci, and let's create our own new list!:

julio@juliohome:~/haskell/blog/mylist$ ghci Main.hs
GHCi, version 7.6.3 [NG/7.6.3.5]: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( Main.hs, interpreted )
Ok, modules loaded: Main.
*Main> cons 1 (cons 2 (cons 3 nil))
Cons 1 (Cons 2 (Cons 3 Empty))