List processing

List - an abstract data type that holds items in a given order.

A list is an abstract data type that holds items in a given order. The same item may be be in the same list multiple times. For example the following are lists:

[9,2,3,4,4,3,7,8]

[65,75,3,65,0]

["cabbage", "potato", "boat", "helmet", "boat"]

An empty list is defined by empty parenthesis:

[]

Lists can also contain other lists:

[[1,2,3], [6,3,8], [9,10,3]]

In Haskell the items contained in a list must all be of the same datatype.

Extension: Data types and lists Whilst some programming languages such as Haskell will only allow datatype for the items in a list, it is sometimes possible to have multiple datatypes in a list. Whilst this might be possible it might not be a good idea and can make some very hard to debug code. For example, in python we might have an unexpected output from some very simple looking code: .> myList = ['-92', 9, 5] .> min(myList) 5

Making and checking a list

You can perform a range of functions on lists:

You can make an empty list:

.> someList = []
.> someList
[]

You can make a list that contains items:

myList = [20,3,51,6,3,7]

You can get the length of a list:

.> myList = [20,3,51,6,3,7]
.> length myList
6

You can check if a list is empty

.> myList = [20,3,51,6,3,7]
.> null myList
False

.> someList = []
.> null myList
True

Chopping up a list

Head - the first element in a list.

Tail - every element in a list apart from the head.

Some very common list commands are head and tail. If you treat a list like a snake, head will give you the first item in the list (its head), and tail will remove the head of the snake and give you the rest a new list.

snake analogy for traversing a list

.> myList = [20,3,51,6,3,7]
.> head(myList)
20

.> myList = [20,3,51,6,3,7]
.> tail(myList)
[3, 51, 6, 3, 7]

You can combine multiple head and tail commands together

.> myList = [20,3,51,6,3,7]
.> head(tail(tail(myList)))
51

Example: combining multiple head and tail commands In the above example we start from the innermost function, in this case tail(...) and work our way outwards. head(tail(tail(myList))) The command tail(myList) takes the first item off myList and returns the rest: [3,51,6,3,7]. We can then replace tail(myList) with this returned list: head(tail([3,51,6,3,7])) We now move to next innermost function: head(tail([3,51,6,3,7])) The command tail([3,51,6,3,7]) takes the first item off [3,51,6,3,7] and returns the rest: [51,6,3,7]. We can then replace tail([3,51,6,3,7]) with this returned list: head([51,6,3,7]) This leaves us with only one more function to calculate. We know the head function returns the first item of a given list. In this case it takes the first item of [51,6,3,7], giving: 51

Adding to lists

Prepend (:) an item to another list, i.e. stick a single element on the front, add a new head to a list:

.> myList = [20,3,51,6,3,7]
.> 5 : myList
[5, 20, 3, 51, 6, 3, 7]
.> "c" : ["a", "t"]
["c", "a", "t"]
.> 1 : 2 : myList
[1, 2, 20, 3, 51, 6, 3, 7]

Extension: Type mismatch when dealing with strings, characters and lists You might be used to other programming languages treating single and double quotation marks in much the same way, for example in Javascript: .> a = "Double quotation marks with a single (') in the middle" .> b = 'Single quotation marks with a double (") in the middle' .> a == b True This isn't the case for Haskell. Haskell treats the single quotation mark (') as defining a single element, and the double quotation marks (") as defining a list, even if there is only a single element inside the double speech marks, e.g. "c". This means that it treats 'c' as a single item of type Char and "c" as a list of type Char. If we make sure that we match our datatypes we will be fine. ['c', 'a', 't'] is the equivalent of "cat" .> "cat" "cat" .> ['c','a','t'] "cat" .> ['c','a','t'] == "cat" True But ["c", "a", "t"] is not the equivalent of "cat", as ["c", "a", "t"] is a list of lists of type Char, whilst "cat" is a list of Char. We can see this mismatch when trying the following: .> ["c","a","t"] == "cat" error: * Couldn't match type `Char' with `[Char]' Expected type: [[Char]] Actual type: [Char] And we can see that ["c", "a", "t"] is a list of lists of type Char by doing: .> ["c","a","t"] == [['c'],['a'],['t']] True Prepending the list "c" to the list ["a", "t"] is fine, as the type of the prepended item, a list of Char, matches the type of the list items it is being prepended to, i.e. lists of type Char: .> "c" : ["a", "t"] ["c", "a", "t"] We can also do the same when prepending an item of type Char, 'c', to a list of type Char, ['a', 't']: .> 'c' : ['a', 't'] "cat" But attempting to prepend an item of type Char 'c' to a list of type List Char ["a", "t"] will not work. The error message here show the difference between the type Char and the type list of Char, defined in the error message by [Char]: .> 'c' : ["a", "t"] * Couldn't match expected type `Char' with actual type `[Char]' * In the expression: "a" In the second argument of `(:)', namely `["'a", "t"]' In the expression: 'c' : ["'a", "t"]

Append (++) an item or a list to another list, i.e. stick something on the end, maybe an item or another list:

.> myList = [20,3,51,6,3,7]
.> myList ++ 99
[20, 3, 51, 6, 3, 7, 99]
.> myList ++ [5, 4, 3, 2]
[20, 3, 51, 6, 3, 7, 5, 4, 3, 2]

The prepend command (:) only allows you to add a single element onto the front of a list. If you want to add a list onto the front of another list you can use the append (++) command:

.> listA = ["x", "y", "z"]
.> listB = ["d", "c"]
.> listA ++ ["e"]
["x", "y", "z", "e"]
.> listA ++ listB
["x", "y", "z", "d", "c"]

You can use a combination of append and prepend to combine multiple lists and items

.> "hello" ++ " " ++ "world"
"hello world"
.> '!' : "shocking" ++ "this" ++ ['w', 'o', 'r', 'k', 's'] ++ "!"
"!shockingthisworks!"

Exercise: Lists What does the following haskell code output: myList = [3,4,5,3,4,6] head(tail(tail(myList))) Answer: 5 What does the following haskell code output: myList = ['a', 'b', 'c', 'd'] tail(myList) Answer: ['b', 'c', 'd'] or "bcd" What does the following haskell code output: myList = ["cat", "mouse", "moose", "cow", "sheep"] length(tail(tail(tail(myList)))) Answer: 2 What does the following haskell code output: myList = ["red", "orange", "yellow", "green", "blue", "indigo", "violet"] null(head(tail(tail(myList)))) length(tail(head(tail(tail(myList ++ ["black", "white"]))))) Answer: False 5 Note that when we take the tail of a single element list containing a string, it treats the string as a list. Given a list called containsPrime which has the values [6,8,9,7,15,21], only using the head and tail commands write some haskell to return the number 7 Answer: head(tail(tail(tail(containsPrime)))) Given a list called someList which has the values ["badger", "fish", "vole"], only using the head, tail and append (++) commands write some haskell to return the list ["vole", "frog"] Answer: let someList = ["badger", "fish", "vole"] tail(tail(someList ++ ["frog"])) What does the following code do: .> listA = [1, 2, 3] .> listB = [9, 8] .> listA ++ tail(listB) .> tail(tail(listA) ++ tail(listB)) Answer: [1,2,3,8] [3,8] What does the following code do: .> listA = ['o', 'x', 'p', 'e'] .> 'r' : [head(listA)] ++ tail(tail(listA)) Answer: "vape" OR ['r', 'o', 'p', 'e']