# F Sharp Programming/Lists

F# : Lists |

A **list** is an ordered collection of related values, and is roughly equivalent to a linked list data structure used in many other languages. F# provides a module, `Microsoft.FSharp.Collections.List`

, for common operations on lists; this module is imported automatically by F#, so the `List`

module is already accessible from every F# application.

## Creating Lists[edit]

### Using List Literals[edit]

There are a variety of ways to create lists in F#, the most straightforward method being a semicolon-delimited sequence of values. Here's a list of numbers in fsi:

> let numbers = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10];; val numbers : int list > numbers;; val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

Notice that all values in a list must have the same type:

> [1; 2; 3; 4; "cat"; 6; 7];; -------------^^^^^^ stdin(120,14): error FS0001: This expression has type string but is here used with type int.

### Using the `::`

("cons") Operator[edit]

It is very common to build lists up by prepending or consing a value to an existing list using the `::`

operator:

> 1 :: 2 :: 3 :: [];; val it : int list = [1; 2; 3]

*Note*: the`[]`

is an empty list. By itself, it has the type`'T list`

; since its used with`int`

s, it has the type`int list`

.

The `::`

operator prepends items to a list, returning a new list. It is a right-associative operator with the following type:

`val inline (::) : 'T -> 'T list -> 'T list`

This operator does not actually mutate lists, it creates an entirely new list with the prepended element in the front. Here's an example in fsi:

> let x = 1 :: 2 :: 3 :: 4 :: [];; val x : int list > let y = 12 :: x;; val y : int list > x;; val it : int list = [1; 2; 3; 4] > y;; val it : int list = [12; 1; 2; 3; 4]

Consing creates a new list, but it reuses nodes from the old list, so consing a list is an extremely efficient O(1) operation.

### Using List.init[edit]

The `List`

module contains a useful method, `List.init`

, which has the type

`val init : int -> (int -> 'T) -> 'T list`

The first argument is the desired length of the new list, and the second argument is an initializer function which generates items in the list. `List.init`

is used as follows:

> List.init 5 (fun index -> index * 3);; val it : int list = [0; 3; 6; 9; 12] > List.init 5 (fun index -> (index, index * index, index * index * index));; val it : (int * int * int) list = [(0, 0, 0); (1, 1, 1); (2, 4, 8); (3, 9, 27); (4, 16, 64)]

F# calls the initializer function `5`

times with the index of each item in the list, starting at index `0`

.

### Using List Comprehensions[edit]

List comprehensions refers to special syntactic constructs in some languages used for generating lists. F# has an expressive list comprehension syntax, which comes in two forms, ranges and generators.

Ranges have the constructs `[start .. end]`

and `[start .. step .. end]`

. For example:

> [1 .. 10];; val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] > [1 .. 2 .. 10];; val it : int list = [1; 3; 5; 7; 9] > ['a' .. 's'];; val it : char list = ['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'; 'i'; 'j'; 'k'; 'l'; 'm'; 'n'; 'o'; 'p'; 'q'; 'r'; 's']

Generators have the construct `[for x in collection do ... yield expr]`

, and they are much more flexible than ranges. For example:

> [ for a in 1 .. 10 do yield (a * a) ];; val it : int list = [1; 4; 9; 16; 25; 36; 49; 64; 81; 100] > [ for a in 1 .. 3 do for b in 3 .. 7 do yield (a, b) ];; val it : (int * int) list = [(1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (2, 3); (2, 4); (2, 5); (2, 6); (2, 7); (3, 3); (3, 4); (3, 5); (3, 6); (3, 7)] > [ for a in 1 .. 100 do if a % 3 = 0 && a % 5 = 0 then yield a];; val it : int list = [15; 30; 45; 60; 75; 90]

Its possible to loop over any collection, not just numbers. This example loops over a `char list`

:

> let x = [ 'a' .. 'f' ];; val x : char list > [for a in x do yield [a; a; a] ];; val it : char list list = [['a'; 'a'; 'a']; ['b'; 'b'; 'b']; ['c'; 'c'; 'c']; ['d'; 'd'; 'd']; ['e'; 'e'; 'e']; ['f'; 'f'; 'f']]

Note that the `yield`

keyword pushes a single value into a list. Another keyword, `yield!`

, pushes a collection of values into the list. The `yield!`

keyword is used as follows:

> [for a in 1 .. 5 do yield! [ a .. a + 3 ] ];; val it : int list = [1; 2; 3; 4; 2; 3; 4; 5; 3; 4; 5; 6; 4; 5; 6; 7; 5; 6; 7; 8]

Its possible to mix the `yield`

and `yield!`

keywords:

> [for a in 1 .. 5 do match a with | 3 -> yield! ["hello"; "world"] | _ -> yield a.ToString() ];; val it : string list = ["1"; "2"; "hello"; "world"; "4"; "5"]

#### Alternative List Comprehension Syntax[edit]

The samples above use the `yield`

keyword explicitly, however F# provides a slightly different arrow-based syntax for list comprehensions:

> [ for a in 1 .. 5 -> a * a];; val it : int list = [1; 4; 9; 16; 25] > [ for a in 1 .. 5 do for b in 1 .. 3 -> a, b];; val it : (int * int) list = [(1, 1); (1, 2); (1, 3); (2, 1); (2, 2); (2, 3); (3, 1); (3, 2); (3, 3); (4, 1); (4, 2); (4, 3); (5, 1); (5, 2); (5, 3)] > [ for a in 1 .. 5 ->> [1 .. 3] ];; val it : int list = [1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3]

`->`

and `->>`

are equivalent to the `yield`

and `yield!`

operators respectively. While its still common to see list comprehensions expressed using `->`

and `->>`

, those constructs will not be emphasized in this book since they have been deprecated in favor of `yield`

and `yield!`

.

## Pattern Matching Lists[edit]

You use the same syntax to match against lists that you use to create lists. Here's a simple program:

let rec sum total = function | [] -> total | hd :: tl -> sum (hd + total) tl let main() = let numbers = [ 1 .. 5 ] let sumOfNumbers = sum 0 numbers printfn "sumOfNumbers: %i" sumOfNumbers main()

The `sum`

method has the type `val sum : int -> int list -> int`

. It recursively enumerates through the list, adding each item in the list to the value `total`

. Step by step, the function works as follows:

total | input | hd :: tl | sum (hd + total) tl |
---|---|---|---|

0 | [1; 2; 3; 4; 5] | 1 :: [2; 3; 4; 5] | sum (1 + 0 = 1) [2; 3; 4; 5] |

1 | [2; 3; 4; 5] | 2 :: [3; 4; 5] | sum (2 + 1 = 3) [3; 4; 5] |

3 | [3; 4; 5] | 3 :: [4; 5] | sum (3 + 3 = 6) [4; 5] |

6 | [4; 5] | 4 :: [5] | sum (4 + 6 = 10) [5] |

10 | [5] | 5 :: [] | sum (5 + 10 = 15) [] |

15 | [] | n/a | returns total |

### Reverse A List[edit]

Frequently, we use recursion and pattern matching to generate new lists from existing lists. A simple example is reversing a list:

let reverse l = let rec loop acc = function | [] -> acc | hd :: tl -> loop (hd :: acc) tl loop [] l

*Note to beginners:*the pattern seen above is very common. Often, when we iterate through lists, we want to build up a new list. To do this recursively, we use an*accumulating parameter*(which is called`acc`

above) which holds our new list as we generate it. Its also very common to use a nested function, usually named`innerXXXXX`

or`loop`

, to hide the implementation details of the function from clients (in other words, clients should not have to pass in their own accumulating parameter).

`reverse`

has the type `val reverse : 'a list -> 'a list`

. You'd use this function as follows:

> reverse [1 .. 5];; val it : int list = [5; 4; 3; 2; 1]

This simple function works because items are always prepended to the accumulating parameter `acc`

, resulting in series of recursive calls as follows:

acc | input | loop (hd :: acc) tl |
---|---|---|

[] | [1; 2; 3; 4; 5] | loop (1 :: []) [2; 3; 4; 5] |

[1] | [2; 3; 4; 5] | loop (2 :: [1]) [3; 4; 5] |

[2; 1] | [3; 4; 5] | loop (3 :: [2; 1]) [4; 5] |

[3; 2; 1] | [4; 5] | loop (4 :: [3; 2; 1]) [5] |

[4; 3; 2; 1] | [5] | loop (5 :: [4; 3; 2; 1]) [] |

[5; 4; 3; 2; 1] | [] | returns acc |

`List.rev`

is a built-in function for reversing a list:

> List.rev [1 .. 5];; val it : int list = [5; 4; 3; 2; 1]

### Filter A List[edit]

Oftentimes, we want to filter a list for certain values. We can write a filter function as follows:

open System let rec filter predicate = function | [] -> [] | hd :: tl -> match predicate hd with | true -> hd::filter predicate tl | false -> filter predicate tl let main() = let filteredNumbers = [1 .. 10] |> filter (fun x -> x % 2 = 0) printfn "filteredNumbers: %A" filteredNumbers main()

The `filter`

method has the type `val filter : ('a -> bool) -> 'a list -> 'a list`

. The program above outputs:

filteredNumbers: [2; 4; 6; 8; 10]

We can make the `filter`

above tail-recursive with a slight modification:

let filter predicate l = let rec loop acc = function | [] -> acc | hd :: tl -> match predicate hd with | true -> loop (hd :: acc) tl | false -> loop (acc) tl List.rev (loop [] l)

*Note:*Since accumulating parameters often build up lists in reverse order, its very common to see`List.rev`

called immediately before returning a list from a function to put it in correct order.

### Mapping Lists[edit]

We can write a function which maps a list to another list:

open System let rec map converter = function | [] -> [] | hd :: tl -> converter hd::map converter tl let main() = let mappedNumbers = [1 .. 10] |> map ( fun x -> (x * x).ToString() ) printfn "mappedNumbers: %A" mappedNumbers main()

`map`

has the type `val map : ('a -> 'b) -> 'a list -> 'b list`

. The program above outputs:

mappedNumbers: ["1"; "4"; "9"; "16"; "25"; "36"; "49"; "64"; "81"; "100"]

A tail-recursive map function can be written as:

let map converter l = let rec loop acc = function | [] -> acc | hd :: tl -> loop (converter hd :: acc) tl List.rev (loop [] l)

Like the example above, we use the accumulating-param-and-reverse pattern to make the function tail recursive.

## Using the `List`

Module[edit]

Although a reverse, filter, and map method were implemented above, its much more convenient to use F#'s built-in functions:

** List.rev** reverses a list:

> List.rev [1 .. 5];; val it : int list = [5; 4; 3; 2; 1]

** List.filter** filters a list:

> [1 .. 10] |> List.filter (fun x -> x % 2 = 0);; val it : int list = [2; 4; 6; 8; 10]

** List.map** maps a list from one type to another:

> [1 .. 10] |> List.map (fun x -> (x * x).ToString());; val it : string list = ["1"; "4"; "9"; "16"; "25"; "36"; "49"; "64"; "81"; "100"]

`List.append`

and the `@`

Operator[edit]

`List.append`

has the type:

val append : 'T list -> 'T list -> 'T list

As you can imagine, the `append`

functions appends one list to another. The `@`

operator is an infix operator which performs the same function:

let first = [1; 2; 3;] let second = [4; 5; 6;] let combined1 = first @ second (* returns [1; 2; 3; 4; 5; 6] *) let combined2 = List.append first second (* returns [1; 2; 3; 4; 5; 6] *)

Since lists are immutable, appending two lists together requires copying all of the elements of the lists to create a brand new list. However, since lists are immutable, its only necessary to copy the elements of the first list; the second list does not need to be copied. Represented in memory, appending two lists can be diagrammed as follows:

We start with the following:

first = 1 :: 2 :: 3 :: [] second = 4 :: 5 :: 6 :: []

Appending the two lists, `first @ second`

, results in the following:

first = 1 :: 2 :: 3 :: [] \______ ______/ \/ combined = 1 :: 2 :: 3 :: second (copied)

In other words, F# prepends a copy of `first`

to `second`

to create the `combined`

list. This hypothesis can be verified using the following in fsi:

> let first = [1; 2; 3;] let second = [4; 5; 6;] let combined = first @ second let secondHalf = List.tail (List.tail (List.tail combined));; val first : int list val second : int list val combined : int list val secondHalf : int list > System.Object.ReferenceEquals(second, secondHalf);; val it : bool = true

The two lists `second`

and `secondHalf`

are literally the same object in memory, meaning F# reused the nodes from `second`

when constructing the new list `combined`

.

Appending two lists, `list1`

and `list2`

has a space and time complexity of O(list1.Length).

`List.choose`

[edit]

`List.choose`

has the following definition:

val choose : ('T -> 'U option) -> 'T list -> 'U list

The `choose`

method is clever because it filters and maps a list simultaneously:

> [1 .. 10] |> List.choose (fun x -> match x % 2 with | 0 -> Some(x, x*x, x*x*x) | _ -> None);; val it : (int * int * int) list = [(2, 4, 8); (4, 16, 64); (6, 36, 216); (8, 64, 512); (10, 100, 1000)]

`choose`

filters for items that return `Some`

and maps them to another value in a single step.

`List.fold`

and `List.foldBack`

[edit]

`List.fold`

and `List.foldBack`

have the following definitions:

val fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State val foldBack : ('T -> 'State -> 'State) -> 'T list -> 'State -> 'State

A "fold" operation applies a function to each element in a list, aggregates the result of the function in an accumulator variable, and returns the accumulator as the result of the fold operation. This description makes fold operations sound more complicated, but the implementation is actually very simple:

(* List.fold implementation *) let rec fold (f : 'State -> 'T -> 'State) (seed : 'State) = function | [] -> seed | hd :: tl -> fold f (f seed hd) tl (* List.foldBack implementation *) let rec foldBack (f : 'T -> 'State -> 'State) (items : 'T list) (seed : 'State) = match items with | [] -> seed | hd :: tl -> f hd (foldBack f tl seed)

`fold`

applies a function to each element in the from left to right, while `foldBack`

applies a function to each element from right to left. Let's examine the fold functions in more technical detail using the following example:

let input = [ 2; 4; 6; 8; 10 ] let f accumulator input = accumulator * input let seed = 1 let output = List.fold f seed input

The value of `output`

is `3840`

. This table demonstrates how `output`

was calculated:

accumulator | input | f accumulator input = accumulator * input |
---|---|---|

1 (seed) | 2 | 1 * 2 = 2 |

2 | 4 | 2 * 4 = 8 |

8 | 6 | 8 * 6 = 48 |

48 | 8 | 48 * 8 = 384 |

384 | 10 | 384 * 10 = 3840 (return value) |

`List.fold`

passes an accumulator with an item from the list into a function. The output of the function is passed as the accumulator for the next item.

As shown above, the `fold`

function processes the list from the first item to the last item in the list, or left to right. As you can imagine, `List.foldBack`

works the same way, but it operates on lists from right to left. Given a fold function `f`

and a list `[1; 2; 3; 4; 5]`

, the fold methods transform our lists in the following ways:

`fold`

:`f (f (f (f (f (f seed 1) 2) 3) 4) 5`

`foldBack`

:`f 1 (f 2 (f 3(f 4(f 5 seed))))`

There are several other functions in the `List`

module related to folding:

`fold2`

and`foldBack2`

: folds two lists together simultaneously.`reduce`

and`reduceBack`

: same as`fold`

and`foldBack`

, except it uses the first (or last) element in the list as the seed value.`scan`

and`scanBack`

: similar to`fold`

and`foldBack`

, except it returns all of the intermediate values as a list rather than the final accumulated value.

Fold functions can be surprisingly useful:

**Summing the numbers 1 - 100**

let x = [ 1 .. 100 ] |> List.fold ( + ) 0 (* returns 5050 *)

In F#, mathematical operators are no different from functions. As shown above, we can actually pass the addition operator to the `fold`

function, because the `+`

operator has the definition `int -> int -> int`

.

**Computing a factorial**

let factorial n = [ 1I .. n ] |> List.fold ( * ) 1I let x = factorial 13I (* returns 6227020800I *)

**Computing population standard deviation**

let stddev (input : float list) = let sampleSize = float input.Length let mean = (input |> List.fold ( + ) 0.0) / sampleSize let differenceOfSquares = input |> List.fold ( fun sum item -> sum + Math.Pow(item - mean, 2.0) ) 0.0 let variance = differenceOfSquares / sampleSize Math.Sqrt(variance) let x = stddev [ 5.0; 6.0; 8.0; 9.0 ] (* returns 1.58113883 *)

`List.find`

and `List.tryFind`

[edit]

`List.find`

and `List.tryfind`

have the following types:

val find : ('T -> bool) -> 'T list -> 'T val tryFind : ('T -> bool) -> 'T list -> 'T option

The `find`

and `tryFind`

methods return the first item in the list for which the search function returns `true`

. They only differ as follows: if no items are found that meet the search function, `find`

throws a `KeyNotFoundException`

, while `tryfind`

returns `None`

.

The two functions are used as follows:

> let cities = ["Bellevue"; "Omaha"; "Lincoln"; "Papillion"; "Fremont"];; val cities : string list = ["Bellevue"; "Omaha"; "Lincoln"; "Papillion"; "Fremont"] > let findStringContaining text (items : string list) = items |> List.find(fun item -> item.Contains(text));; val findStringContaining : string -> string list -> string > let findStringContaining2 text (items : string list) = items |> List.tryFind(fun item -> item.Contains(text));; val findStringContaining2 : string -> string list -> string option > findStringContaining "Papi" cities;; val it : string = "Papillion" > findStringContaining "Hastings" cities;; System.Collections.Generic.KeyNotFoundException: The given key was not present in the dictionary. at Microsoft.FSharp.Collections.ListModule.find[T](FastFunc`2 predicate, FSharpList`1 list) at <StartupCode$FSI_0007>.$FSI_0007.main@() stopped due to error > findStringContaining2 "Hastings" cities;; val it : string option = None

## Exercises[edit]

### Pair and Unpair[edit]

Write two functions with the following definitions:

val pair : 'a list -> ('a * 'a) list val unpair : ('a * 'a) list -> 'a list

The `pair`

function should convert a list into a list of pairs as follows:

pair [ 1 .. 10 ] = [(1, 2); (3, 4); (5, 6); (7, 8); (9, 10)] pair [ "one"; "two"; "three"; "four"; "five" ] = [("one", "two"); ("three", "four")]

The `unpair`

function should convert a list of pairs back into a traditional list as follows:

unpair [(1, 2); (3, 4); (5, 6)] = [1; 2; 3; 4; 5; 6] unpair [("one", "two"); ("three", "four")] = ["one"; "two"; "three"; "four"]

### Expand a List[edit]

Write a function with the following type definition:

val expand : 'a list -> 'a list list

The `expand`

function should expand a list as follows:

expand [ 1 .. 5 ] = [ [1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5] ] expand [ "monkey"; "kitty"; "bunny"; "rat" ] = [ ["monkey"; "kitty"; "bunny"; "rat"]; ["kitty"; "bunny"; "rat"]; ["bunny"; "rat"]; ["rat"] ]

### Greatest common divisor on lists[edit]

The task is to calculate the greatest common divisor of a list of integers.

The first step is to write a function which should have the following type:

val gcd : int -> int -> int

The `gcd`

function should take two integers and return their greatest common divisor. Hint: Use Euler's algorithm

gcd 15 25 = 5

The second step is to use the gcd function to calculate the greatest common divisor of an int list.

val gcdl : int list -> int

The `gcdl`

function should work like this:

gcdl [15; 75; 20] = 5

If the list is empty the result shall be 0.

### Basic Mergesort Algorithm[edit]

The goal of this exercise is to implement the mergesort algorithm to sort a list in F#. When I talk about sorting, it means sorting in an ascending order. If you're not familiar with the mergesort algorithm, it works like this:

- Split: Divide the list in two equally large parts
- Sort: Sort those parts
- Merge: Sort while merging (hence the name)

Note that the algorithm works recursively. It will first split the list. The next step is to sort both parts. To do that, they will be split again and so on. This will basically continue until the original list is scrambled up completely. Then recursion will do its magic and assemble the list from the bottom. This might seem confusing at first, but you will learn a lot about how recursion works, when there's more than one function involved

The `split`

function

val split : 'a list -> 'a list * 'a list

The `split`

function will work like this.

split [2; 8; 5; 3] = ( [5; 2], [8; 3] )

The splits will be returned as a tuple. The `split`

function doesn't need to sort the lists though.

The `merge`

function

The next step is merging. We now want to merge the splits together into a sorted list assuming that both splits themselves are already sorted. The `merge`

function will take a tuple of two already sorted lists and recursively create a sorted list:

val merge : 'a list * 'a list -> 'a list

Example:

merge ( [2; 5], [3; 8] ) = [2; 3; 5; 8]

It is important to notice that the `merge`

function will only work if both splits are already sorted. It will make its implementation a lot easier. Assuming both splits are sorted, we can just look at the first element of both splits and only compare which one of them is smaller. To ensure this is the case we will write one last function.

The `msort`

function

You can think of it as the function organising the correct execution of the algorithm. It uses the previously implemented functions, so it's able to take a random list and return the sorted list.

val msort : 'a list -> 'a list

How to implement msort:

If the list is empty or if the list has only one element, we don't need to do anything to it and can immediately return it, because we don't need to sort it.

If that's not the case, we need to apply our algorithm to it. First `split`

the list into a tuple of two, then `merge`

the tuple while recursively sorting both arguments of the tuple