Lists

The types used for storing collections of values are list and array. F# list is a typical linked-list type known from many functional languages – it can be either an empty list (written as []) or a cell containing a value and a reference to the tail, which is itself a list (written as value::tail). It is also possible to write a list using a simplified syntax, which means that you can write [1; 2; 3] instead of 1::2::3::[] (which is exactly the same list written just using the two basic list constructors). Array is a .NET compatible mutable array type, which is stored in a continuous memory location and is therefore very efficient – being a mutable type, array is often used in imperative programming style, which will be discussed later. The following example shows declaration of a list value and an implementation of a recursive function that adds together all elements in the list:


> let nums = [1; 2; 3; 4; 5];;
val nums : list
> let rec sum list =
match list with
| h::tail -> (sum tail) + h
| [] -> 0
val sum : list -> int


Similarly as earlier we declared a recursive function using let rec and inside the body we used pattern matching to test whether the list is an empty list or a list cell. Note that list is a generic type, which means that it can store values of any F# type. The type in our example is list, which means that the declared instance of list contains integers. Functions working with generic types can be restricted to some specific type - for example the sum function above requires a list of integers that can be added (this is inferred by the type inference, because the default type used with the + operator is int). Alternatively, the function can be generic as well, which means that it works with any lists - for example a function that returns the last element in the list doesn’t depend on the type and so it can be generic. The signature of a generic function to return the last element would be last : list<'a> -> 'a. An important feature when writing recursive functions in F# is the support for tail-calls. This means that when the last operation performed by the function is a call to a function (including a recursive call to itself), the runtime drops the current stack frame, because it isn’t needed anymore - the value returned by the called function is a result of the caller. This minimizes a chance for getting a stack overflow exception. The sum function from the previous example can be written using an auxiliary function that uses a tail recursion as following:

> // 'acc' is usually called an 'accumulator' variable
let rec sumAux acc list =
match list with
| h::tail -> sumAux (acc + h) tail
| [] -> acc
val sum : int -> list -> int
> let sum list = sumAux 0 list
val sum : list -> int