Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 8 other subscribers.

Lists

Lists were mentioned in a previous post but we need to look at them in more detail considering how often they will be used when creating Functional programs.

A list is considered as a composite data type meaning that it brings together one or more of the primative data types of the language you are using. We can then access an element of the list by referring to its index value. Lists in Haskell are homogenous meaning that all elements have to be of the same data type. If you want to mix and match elements of different types then you need to create a tuple and not a list.

We can use the let command to define what we want our list to be:

Prelude> let evenNums = [2,4,6,8]
Prelude> evenNums
[2,4,6,8]

Then we can access any element of the list using the list name remembering the first element is index 0:

Prelude> evenNums !! 0
2
Prelude> evenNums !! 2
6

Lists can be joined together using ++:

Prelude> [1,2] ++ [3,4] ++ [5,6]
[1,2,3,4,5,6]

In terms of processing, the list on the left of the ++ operator will always be traversed. The bigger this list is the longer the processing will take so be careful not to do this with long lists. Adding a value to the front of a list using : doesn’t take so long:

Prelude> 0 : evenNums
[0,2,4,6,8]

This is perhaps a good time to start looking at how all of this ties up with the content of the AQA A-level specification. The order of the specification describes Functional Programming in general as well as Function Types and First-class Objects. Lists are right at the end but we are going to consider them first. I often find that when teaching programming you are better to start with familiar concepts before moving to newer, more abstract ones. I would like to think that by A-level pupils have a good idea of data structures such as lists. For me it makes sense to start with pdf page 87 of the specification:

– Be familiar with representing a list as a concatenation of a head and a tail.
– Know that the head is an element of a list and the tail is a list.
– Know that a list can be empty.
Picture of snake
Snakes consist of a head and tail…just like lists.

The structure of a list in Functional Programming is an important consideration. We know that a list can be empty (eg: [ ] is an empty list) and we can add values into it using : or joining other lists using the ++ operator.

A list in FP is considered being made of two parts: the head and the tail. The head is the first element of the list and the tail is the rest of the list without the head (and is a list itself). For example, the list [2,4,6] can be considered as a head of value 2 and a tail [4,6]. Therefore the list is the concatenation of the head and the tail 2:[4,6].

So it follows that a list, as described in the first bullet point, is a concatenation of a head and a tail.

With these facts we can consider the different operations that can be applied to lists and the results when they are evaluated. Again this is all background information and we are only just understanding what Functional Programming languages can do. In later posts I will consider how all of these components can be pulled together in programmed solutions to problems. Following on from pdf page 87 of the specification there are several list operations pupils need to be familiar with:

– return head of list
– return tail of list
– test for empty list
– return length of list
– construct an empty list
– prepend an item to a list
– append an item to a list

These operations are straight-forward enough in Haskell. Firstly, the head function returns just the value at the head of the list:

Prelude> head [1,2,3,4,5]
1

And guess what the tail function does:

Prelude> tail [1,2,3,4,5]
[2,3,4,5]

The null function can be used to check to see if a list is empty or not:

Prelude> null [1,2,3,4,5]
False
Prelude> null []
True

The length of a list can be found using the length function:

Prelude> length [1,2,3,4,5]
5

An empty list can be constructed easily enough:

Prelude> let emptyList = []
Prelude> emptyList
[]

Prepending (putting something at the start of) to a list has been covered before but just to link back to the specification point:

Prelude> 0 : [1,2,3,4,5]
[0,1,2,3,4,5]

And lastly, appending to the end of a list requires you to concatenate two lists. A single value will still have to be described in a list form:

Prelude> [1,2,3,4,5] ++ [6]
[1,2,3,4,5,6]
Prelude> [1,2,3,4,5] ++ [6,7]
[1,2,3,4,5,6,7]

Leave a comment

Your email address will not be published. Required fields are marked *