F#10 : Lists

Any serious programming you do in any language will always involve lists. As such you will be pleased to know that F# has very very good support for Lists, by way of its List module. A list in F# is an ordered, immutable series of elements of the same type.

Creating Lists

In F# there are several ways in which you can create Lists, shown below are a few examples.

• Create an empty list
• Create a simple list containing 1 to 10
• Create a simple list creating odd numbers between 1 and 10, which is achieved using a step operator
• Using a for loop to create a list

let prettyPrint desc list =
    printfn desc
    printfn "%A" list
        

//empty list
let listEmpty = []
//simple list
let list1 = [1 .. 10 ]
//simple list, with step value
let list2 = [1 ..2..10 ]
//using for loops to create lists
let list3 = [for i in 1 .. 10 -> i*2 ]



prettyPrint "let listEmpty = []" listEmpty
prettyPrint "let list1 = [ 1 .. 10 ]" list1
prettyPrint "let list2 = [ 1 .. 2..10 ]" list2
prettyPrint "[ for i in 1 .. 10 -> i*2 ]" list3

Which when run will give the following results:

List Comprehensions

The last example in the one above showed how to use a for loop to create a list, which is very cool, but there is something even more cool and powerful within the F# toolbox, which are "List Comprehensions".

"List Comprehensions" are a powerful technique that allow you to create lists by using pretty much and of the standard F#, which includes functions/loops/conditions etc.

Let's continue to have a look at example of how we might construct lists using list comprehensions.

let is2 x = match x with
    | 2 -> "YES"
    | _ -> "NO"



//yield directly
let list1 = [
    yield 1;
    yield 2;
    yield 3;
]

//yield numbers between 1 and 20 where we use the
//Math.Pow function to return a new number
let list2 = [for i in 1.0 .. 20.0 do
                yield Math.Pow(i,2.0)
            ]
    
//yield only numbers between 1 and 20 that 
//can be divided by 5
let list3 = [
                for i in 1 .. 20 do
                    if i % 5 = 0 then
                        yield i
            ]


//yields YES/NO strings depending on
//whether source int = 2 or not
let list4 = [for i in 1 .. 5 ->
                is2 i
            ]

Which prints this when run

Some Useful List Operators

Cons Operator

We can use the cons operator "::" to append values to an existing list, so suppose we had this list

let list1 = [1;2;3;4]
let list2 = 42 :: list1

Which gives this result

Concat Operator

Another quite useful operator is the "@" operator, which allows you to concatenate lists that have the same type. So for example if we had this

let list1 = [1;2;3;4]
let list2 = [5;6;7;8]
let list3 = list1 @ list2

We would get the following results

The List Module

I don’t think I am overplaying things when I say that the List module is a pivotal module in the F# landscape. I fact the MSDN documentation for the List module is extremely good when compared to other areas in F#. As such I don’t think I will be able to add much value to some of the examples found on MSDN, but I will include a few here for your convenience, but for more information you should examine MSDN : http://msdn.microsoft.com/en-us/library/dd233224.aspx

Properties

A list has a number of useful properties which are quite useful, which are shown in the table below:

Where we can see example usage of these as follows:

let list1 = [ 1; 2; 3 ]

// Properties
printfn "list1.IsEmpty is %b" (list1.IsEmpty)
printfn "list1.Length is %d" (list1.Length)
printfn "list1.Head is %d" (list1.Head)
printfn "list1.Tail.Head is %d" (list1.Tail.Head)
printfn "list1.Tail.Tail.Head is %d" (list1.Tail.Tail.Head)
printfn "list1.Item(1) is %d" (list1.Item(1))

Which when run, will give the following results:

There are also many (too many for one blog, but we will go through a few, for the rest MSDN is actually very on) functions that are available in the F# List module. In fact the MSDN page for the List module is excellent, and has an example for each list module function, as such I would urge you to peruse MSDN for a look at what you can do.

The MSDN page is here : http://msdn.microsoft.com/en-us/library/ee353738.aspx

We will however look at a few examples here, for fun like (note I have taken most of these examples straight from MSDN)

Filter

Returns a new collection containing only the elements of the collection for which the given predicate returns true.Here is a trivial example that only picks even numbers from a list to produce a new list

let evenOnlyList = List.filter (fun x -> x % 2 = 0) [1; 2; 3; 4; 5; 6]

Which when run looks like this:

Find

Returns the first element for which the given function returns true. In this example since a list of 1 to 100 contains 5, 5 is the 1st number that is divisible by 5 so it is the return value

let isDivisibleBy number elem = elem % number = 0
let result = List.find (isDivisibleBy 5) [ 1 .. 100 ]

Which when run looks like this:

Forall

Tests if all elements of the collection satisfy the given predicate. In this example the entire list needs to contain 0s to get a true return value.

let isAllZeroes list = List.forall (fun elem -> elem = 0.0) list
printfn "%b" (isAllZeroes [0.0; 0.0])
printfn "%b" (isAllZeroes [0.0; 1.0])

Which when run looks like this:

Iteri

Applies the given function to each element of the collection. The integer passed to the function indicates the index of element.

let data = ["Cats";"Dogs";"Mice";"Elephants"]
data |> List.iteri (fun i x -> printfn "item %d: %s" i x)

Which when run looks like this:

SortWith

Sorts the given list using the given comparison function.

let list1 = [ ""; "&"; "&&"; "&&&"; ""; "|"; "||"; "|||" ]
printfn "Before sorting: "
list1 |> printfn "%A" 

//custom sorting function
let sortFunction (string1:string) (string2:string) =
    if (string1.Length > string2.Length) then
        1
    else if (string1.Length  printfn "After sorting:\n%A"

Which when run looks like this:

There are loads of useful functions in the list module this is a mere fraction of what can be found, have a look there are some very useful functions to be found

Pattern Matching Lists

It is also fairly trivial to pattern match against List values, where we can simply do something like this:

In this example we are matching 2 cases

1. List which has a head and tail, which we match using the syntax head :: tail (you don’t have to use the labels "head" and "tail", these are arbitrary labels)
2. Empty list

let printIt desc x = 
    printfn "%A %A" desc x

let patternMatchAList list =
    match list with
    | head :: tail -> 
        printIt "head=" head
        printIt "tail=" tail
    | [] -> ()

patternMatchAList [1;2;3;4;5]
printfn "\r\n\r\n"
patternMatchAList [1;2]
printfn "\r\n\r\n"
patternMatchAList [1]
printfn "\r\n\r\n"

Which gives these results

Small Look At Recursion With Lists

No discussion on F# Lists and pattern matching would be complete without talking about recursion. Now recursion is something I will be dedicating an entire post to, but for now lets see what it takes to write a recursive function that works over a list in F#.

So we have the following code:

let printIt desc x = 
    printfn "%A %A" desc x

let rec printList list =
    match list with
    | h :: t -> 
        printIt "head=" h
        printIt "tail=" t
        printList t
    | [] -> ()


printList [1;2;3;4;5]

Note the use of the rec keyword, that tells the F# compiler that this function will be recursive. Without that keyword, a recursive function call is a compile time error, albeit not a great error message (at least not in my opinion)

So lets see the results of running the good example shown just above with the following list [1;2;3;4;5]

It can be seen that our pattern matching works just fine, and it terminates when it matches an empty list as expected