# List processing

 ← Basics of functional programming List processing Higher order functions →

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.

```.> myList = [20,3,51,6,3,7]
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]
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`

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']