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

Continue

Records

The next data type that we will look at is a record type. It can be viewed as a tuple with named members (in case of record these are called labels), which can be accessed using a dot-notation and as mentioned earlier it is good to use this type when it would be difficult to understand what the members in a tuple represent. One more difference between a record type and a tuple is that records have to be declared in advance using a type construct:


> // Declaration of a record type
    type Product = { Name:string; Price:int };;


> // Constructing a value of the 'Product' type
    let p = { Name="Test"; Price=42; };;
val p : Product


> p.Name;; val it : string = "Test"


> // Creating a copy with different 'Name'
    let p2 = { p with Name="Test2" };;
val p2 : Product



The last command uses an interesting construct - the with keyword. The record types are by default immutable, meaning that the value of the member can’t be modified. Since the members are immutable you will often need to create a copy of the record value with one (or more) modified members. Doing this explicitly by listing all the members would be impractical, because it would make adding a new members very difficult, so F# supports the with keyword to do this.
F# records are in many ways similar to classes and they can be, indeed, viewed as simplified classes. Record types are by default immutable, which also means that F# use a structural comparison when comparing two values of a record type (instead of the default reference comparison used when working with classes) and if you need this behavior (e.g. for storing records as a keys in a dictionary) it is very practical to use them. Also, using a record instead of a class is a good idea in a functional code where you can use the with construct. Exposing a record type in a public interface of the module requires additional care and it is often useful to make the labels available as members, which makes it easier to modify implementation of the type later. This topic will be further discussed in the third part of this article series.

Continue