# A-level Computing/AQA/Paper 2/Fundamentals of functional programming/List processing

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:
You can make a list that contains items:
You can get the length of a list:
You can check if a list is empty

### Chopping up a list

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.
You can combine multiple head and tail commands together
* 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:
* 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:
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:
You can use a combination of append and prepend to combine multiple lists and items
* 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']