Lists in F#

In this post I will talk about the lists in F#, one of the fundamental concepts of the language. What should be said from the very beginning is that list are imutable single linked list. That means whenever you change a list, a new list is created.

You can declare a list in the following ways:

let list1 = [1;2;3;4]

let list2 = 5::6::7::8::[]

To print the content of the list you can do this:

printfn “list1: %a” output_any list1

printfn “list2: %a” output_any list2

list1: [1; 2; 3; 4]
list2: [5; 6; 7; 8]

You can concatenate two lists with operator @:

let list3 = list1 @ list2
printfn "list3: %a" output_any list3

list3: [1; 2; 3; 4; 5; 6; 7; 8]

and you can append elements to the beginning of the list with operator ::

let list4 = -1::0::list3

printfn "list4: %a" output_any list4

list4: [-1; 0; 1; 2; 3; 4; 5; 6; 7; 8]

You can also use the List (defined in Microsoft.FSharp.Code) functionality to print a list by iterating over its elements:

list3: [1; 2; 3; 4; 5; 6; 7; 8]

1 2 3 4

The same can be achieved using the pipe operator:

list1 |> List.iter (fun x -> printf "%d " x)

You can also iterate and get the index of the list elements, with List.iteri:

list1 |> List.iteri (fun i x -> printfn "list1[%d] : %d " i x)

list1[0] : 1
list1[1] : 2
list1[2] : 3
list1[3] : 4

List have a special representation, a head followed by a tail, that is in turn another list (including empty list []). Let's consider the list [1;2;3]. It has the head 1, and the tail [2;3]. The tail, in turn, has the head 2 and the tail [3]. This tail has the head 3 and the tail [], which is the empty list. You can see the head and tail of a list with List.hd and List.td:

printfn "head list1: %a" output_any (List.hd list1)
printfn "tail list1: %a" output_any (List.tl list1)

The ouput for list1 [1;2;3] is:

head list1: 1
tail list1: [2;3]

Enough with basic things. Let's try working with lists.

1. Minimum and maximum from a list

We can compute the maximum (or minimum) of a list using the following algorithm:

• if the list is empty, indicate error
• if the list has only one element, that is the maximum (or minimum)
• if the list has at least to elements, compute the maximum between that element and the maximum from the rest of the list

That sounds like a recursive operation, which can be simply put in F# like this:

let rec greatest_element l =

    match l with

    | [] -> failwith "empty list"

    | [x] -> x

    | x::rest -> max x (greatest_element rest)

let rec smallest_element l =

    match l with

    | [] -> failwith "empty list"

    | [x] -> x

    | x::rest -> min x (smallest_element rest)

We can use that like this:

let list1 = [1;2;3;4;-4;-3;-2;-1]

let list2 = []   

try

   printfn "maximum from list1: %d" (greatest_element list1)

   printfn "minimum from list1: %d" (smallest_element list1)
   printfn "maximum from list2: %d" (greatest_element list2)

   printfn "minimum from list2: %d" (smallest_element list2)

with

   Failure msg ->

      printfn "Error: %s" msg

and the output would be:

maximum from list1: 4

minimum from list1: -4

Error: empty list

2. Reversing a list

How would we reverse a list? We should take the last element and append to it the one before the last. To the new list we append the one before the one before the end, etc. That again sounds recursive.

let rec revert_list l =

   match l with

   | [] -> []

   | x::rest -> (revert_list rest) @ [x]

let list1 = [1;2;3;4;-4;-3;-2;-1]
printfn "list1: %a" output_any list1

printfn "list2: %a" output_any (revert_list list1)

And here is the output:

list1: [1; 2; 3; 4; -4; -3; -2; -1]

list2: [-1; -2; -3; -4; 4; 3; 2; 1]

3. Inserting in a list

So how could we insert an element in a list, before or after a specified element? We can use the following algorithm:

• if the list is empty, the new list has one element (the one to insert)
• else, if the head is the element we are looking for, create a list, with the new element either before the head, or between the head and the tail
• else, if the head is not the element we are looking for, append the head to a list created by inserting the new element in the tail.

You got that right, recursion again.

let rec insert_after elem newelem l =

    match l with

    | [] -> [newelem]

    | x::rest -> if x = elem then

                    (x::newelem::rest)

                 else

                     x::(insert_after elem newelem rest)

let rec insert_before elem newelem l =

    match l with

    | [] -> [newelem]

    | x::rest -> if x = elem then

                    (newelem::x::rest)

                 else

                    x::(insert_before elem newelem rest)        
let list1 = [1;2;3;4;-4;-3;-2;-1]

let list2 = insert_after 4 6 list1

let list3 = insert_before 6 5 list2
printfn "list1: %a" output_any list1

printfn "list2: %a" output_any list2

printfn "list3: %a" output_any list3

And the output is:

list1: [1; 2; 3; 4; -4; -3; -2; -1]

list2: [1; 2; 3; 4; 6; -4; -3; -2; -1]

list3: [1; 2; 3; 4; 5; 6; -4; -3; -2; -1]

4. Removing elements from a list

As a last exercise, let's consider the removing of elements from a list. The following steps can be used to remove elements:

• if the list is empty, return an empty list
• if the list is not empty and the head meets the removing criteria, return a list obtained by reiterating the algorithm on the tail of the list
• if the list is not empty and the head does not meet the removing criteria, return a list obtained by appending the head to a list optained by reiterating the algorithm on the tail of the list

let rec remove_if l predicate =

    match l with

    | [] -> []

    | x::rest -> if predicate(x) then

                    (remove_if rest predicate)

                 else

                     x::(remove_if rest predicate)

The great thing about this implementation is that we can pass a lambda expression as a predicate, and use it to specify the criteria for removing elements. We can remove like that, for instance, the odd elements, or the even elements, or the negative elements. Here is some sample code:

let list1 = [1;2;3;4;-4;-3;-2;-1]

let list2 = remove_if list1 (fun x -> (abs x &&&1) = 1)

let list3 = remove_if list1 (fun x -> (abs x &&&1) = 0)

let list4 = remove_if list1 (fun x -> x < 0)

printfn "%a" output_any list1
printfn "%a" output_any list2
printfn "%a" output_any list3
printfn "%a" output_any list4

The output for this sample is:

[1; 2; 3; 4; -4; -3; -2; -1]

[2; 4; -4; -2]

[1; 3; -3; -1]

[1; 2; 3; 4]

I hope this will help you to get a grip on how you can work on lists in F#.