Lists in functional programming
A list is still a collection of values of the same type e.g. integer, string. A list is made up of two parts: the head and tail. The head of the list is the first item in the list. The tail of the list is a list consisting of
the remaining elements. In the list [5,7,2,3,8] the head is 5 and the tail is [7,2,3,8]
We can apply these rules repeatedly e.g. head(tail(tail numbers)). If the original numbers list is [5,7,2,3,8] then the tail of numbers is [7,2,3,8] and the tail of that is [2,3,8] and the head of that is 2 so the
head(tail(tail numbers)) = 2.
List functions
The command null can be applied to a list and will return true if it is empty and false if it is not e.g. names = ["Bill","Bob","Ben"] null(tail(tail names)) is False because it still contains "Ben" but null(tail(tail(tail
names))) is True because it is an empty list.
Prepending to a list means adding elements at the start of the list and appending to a list means adding elements at the end. We can prepend a single item using a colon ("Bruce":names) or prepend another list using ++
(["Bruce","Brad"]++names).
To append to a list we use ++ and append another list of one or more items names++["Eric","Ed"].
Passing a list to the function length e.g. length names would return 3. It is important to remember that names is immutable so still contains the same original three names even after the earlier appending and prepending
operations take place.
Higher order list functions
A function is higher-order if it takes a function as an argument or returns a function as a result, or does both. Three common higher order functions built in to functional programming languages are:
Map
Map is the name of a higher-order function that applies a given function to each element of a list, returning a list of results e.g.
map (*2) [10,20,30,40,50]
This returns a new list [20,40,60,80,100] where each element
in the original list has been multiplied by two.
Filter
Filter is the name of a higher-order function that processes a data structure, typically a list, in some order to produce a new data structure containing exactly those elements of the original data structure that match a given
condition e.g.
filter (>20) [10,20,30,40,50]
The new list produced is [30,40,50].
Fold/reduce
Fold, sometimes called reduce, is the name of a higher-order function which reduces a list of values to a single value by repeatedly applying a combining function to the list values. foldl means to fold values from left to
right and foldr means fold values from right to left. For addition this makes no difference but for division it is a big difference.
