15.md

List

Lists are used to hold zero or more elements of a given type. We have already seen lists in our examples. This time we are going to dive deeper. We will define our own list type to help us understand the built in type.

data List a =
    Nil
  | Cons a (List a)
  deriving (Show, Eq)

List has two data constructors. Nil is used to construct an empty list and Cons is used to insert a new element to the head of a list. We have the same constructors in the built in list type. Nil corresponds to [] and Cons is (:). Open ghci and try out the following snippets.

-- an empty list
[]

-- 4 inserted to the head of an empty list
4:[]

-- building 1, 2, 3, 4 by inserting the elements one by one
1:(2:(3:(4:[])))
1:2:3:4:[]
[1,2,3,4]
[1..4]

Partial functions

The first element of the list is called head and the rest of the list is called tail. Functions with the same name already exist in prelude to extract these values but you should avoid using them. Let's have a look at the type signature.

head :: [a] -> a

The head function needs to return a value of type a. Since the function signature is generic enough, it can not do it any other way than to return an element from the list. What does it return if the list is empty? Since there is nothing to return it throws an exception. If a function is unable to map every possible combination of its parameters to a return value, it is called a partial function. The head function is a partial function. tail suffers from the same flaws and there are many others.

Throwing an exception is a side effect of the function. If your functions have side effects it is much harder to understand how they behave and what are the possible outcomes of your program. Avoid writing functions with side effects by using the proper types that express the needed information as a return value.

A function with the expected behaviour would express the lack of the head element in a type instead of throwing an exception. We already know how to express an optional value.

safeHead :: [a] -> Maybe a

Pattern matching

We will use pattern matching to implement the safeHead function.

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:xs) = Just x

First we match on the empty list constructor. The head of the empty list does not exist so we return Nothing. Then we match on the Cons constructor of the list. In this case x stands for the head element and xs stand for the rest of the list so we return Just x.

Exercise

• Implement the safeTail function.
• What might the following function do? Try to come up with at least three possible solutions. You do not need to implement them.

f :: a -> [a] -> Bool

• What might this do?

g :: a -> [a] -> ([a], [a])