layout: post
title: “Choosing between collection functions”
description: “A guide for the perplexed”

categories: []

There’s more to learning a new language than the language itself. In order to be productive, you need to memorize a big chunk of the standard library
and be aware of most of the rest of it. For example, if you know C#, you can pick up Java-the-language quite quickly, but you won’t really get up to speed
until you are comfortable with the Java Class Library as well.

Similarly, you can’t really be effective in F# until you have some familiarity with all the F# functions that work with collections.

In C# there are only a few LINQ methods you need to know1 (Select, Where, and so on).
But in F#, there are currently almost 100 functions in the List module (and similar counts in the Seq and Array modules). That’s a lot!

1 Yes, there are more, but you can get by with just a few. In F# it’s more important to know them all.

If you are coming to F# from C#, then, the large number of list functions can be overwhelming.

So I have written this post to help guide you to the one you want.
And for fun, I’ve done it in a “Choose Your Own Adventure” style!

Choosing between collection functions - 图1

What collection do I want?

First, a table with information about the different kinds of standard collections. There are five “native” F# ones: list, seq, array, map and set,
and ResizeArray and IDictionary are also often used.









































Immutable?Notes
listYes
Pros:

  • Pattern matching available.

  • Complex iteration available via recursion.

  • Forward iteration is fast. Prepending is fast.


Cons:

  • Indexed access and other access styles are slow.


seqYes

Alias for IEnumerable.


Pros:

  • Lazy evaluation

  • Memory efficient (only one element at a time loaded)

  • Can represent an infinite sequence.

  • Interop with .NET libraries that use IEnumerable.


Cons:

  • No pattern matching.

  • Forward only iteration.

  • Indexed access and other access styles are slow.


arrayNo

Same as BCL Array.


Pros:

  • Fast random access

  • Memory efficient and cache locality, especially with structs.

  • Interop with .NET libraries that use Array.

  • Support for 2D, 3D and 4D arrays


Cons:

mapYesImmutable dictionary. Requires keys to implement IComparable.
setYesImmutable set. Requires elements to implement IComparable.
ResizeArrayNoAlias for BCL List. Pros and cons similar to array, but resizable.
IDictionaryYes

For an alternate dictionary that does not requires elements to implement IComparable,
you can use the BCL IDictionary.
The constructor is dict in F#.


Note that mutation methods such as Add are present, but will cause a runtime error if called.


These are the main collection types that you will encounter in F#, and will be good enough for all common cases.

If you need other kinds of collections though, there are lots of choices:

  • You can use the collection classes in .NET, either the traditional, mutable ones
    or the newer ones such as those in the System.Collections.Immutable namespace.
  • Alternatively, you can use one of the F# collection libraries:
    • FSharpx.Collections, part of the FSharpx series of projects.
    • ExtCore. Some of these are drop-in (almost) replacements for the Map and Set types in FSharp.Core which provide improved performance in specific scenarios (e.g., HashMap). Others provide unique functionality to help tackle specific coding tasks (e.g., LazyList and LruCache).
    • Funq: high performance, immutable data structures for .NET.
    • Persistent: some efficient persistent (immutable) data structures.

About the documentation

All functions are available for list, seq and array in F# v4 unless noted. The Map and Set modules have some of them as well, but I won’t be discussing map and set here.

For the function signatures I will use list as the standard collection type. The signatures for the seq and array versions will be similar.

Many of these functions are not yet documented on MSDN so I’m going to link directly to the source code on GitHub, which has the up-to-date comments.
Click on the function name for the link.

Note on availability

The availability of these functions may depend on which version of F# you use.

  • In F# version 3 (Visual Studio 2013), there was some degree of inconsistency between Lists, Arrays and Sequences.
  • In F# version 4 (Visual Studio 2015), this inconsistency has been eliminated, and almost all functions are available for all three collection types.

If you want to know what changed between F# v3 and F# v4, please see this chart
(from here).
The chart shows the new APIs in F# v4 (green), previously-existing APIs (blue), and intentional remaining gaps (white).

Some of the functions documented below are not in this chart — these are newer still! If you are using an older version of F#,
you can simply reimplement them yourself using the code on GitHub.

With that disclaimer out of the way, you can start your adventure!

Table of contents

1. What kind of collection do you have?

What kind of collection do you have?

  • If you don’t have a collection, and want to create one, go to section 2.
  • If you already have a collection that you want to work with, go to section 9.
  • If you have two collections that you want to work with, go to section 23.
  • If you have three collections that you want to work with, go to section 24.
  • If you have more than three collections that you want to work with, go to section 25.
  • If you want to combine or uncombine collections, go to section 26.

2. Creating a new collection

So you want to create a new collection. How do you want to create it?

  • If the new collection will be empty or will have one element, go to section 3.
  • If the new collection is a known size, go to section 4.
  • If the new collection is potentially infinite, go to section 7.
  • If you don’t know how big the collection will be, go to section 8.

3. Creating a new empty or one-element collection

If you want to create a new empty or one-element collection, use these functions:

If you know the size of the collection in advance, it is generally more efficient to use a different function. See section 4 below.

Usage examples

  1. let list0 = List.empty
  2. // list0 = []
  4. let list1 = List.singleton "hello"
  5. // list1 = ["hello"]

4. Creating a new collection of known size

  • If all elements of the collection will have the same value, go to section 5.
  • If elements of the collection could be different, go to section 6.

5. Creating a new collection of known size with each element having the same value

If you want to create a new collection of known size with each element having the same value, you want to use replicate:

Array.create is basically the same as replicate (although with a subtly different implementation!) but replicate was only implemented for Array in F# v4.

Usage examples

  1. let repl = List.replicate 3 "hello"
  2. // val repl : string list = ["hello"; "hello"; "hello"]
  4. let arrCreate = Array.create 3 "hello"
  5. // val arrCreate : string [] = [|"hello"; "hello"; "hello"|]
  7. let intArr0 : int[] = Array.zeroCreate 3
  8. // val intArr0 : int [] = [|0; 0; 0|]
  10. let stringArr0 : string[] = Array.zeroCreate 3
  11. // val stringArr0 : string [] = [|null; null; null|]

Note that for zeroCreate, the target type must be known to the compiler.

6. Creating a new collection of known size with each element having a different value

If you want to create a new collection of known size with each element having a potentially different value, you can choose one of three ways:

  • init : length:int -> initializer:(int -> 'T) -> 'T list.
    Creates a collection by calling the given generator on each index.
  • For lists and arrays, you can also use the literal syntax such as [1; 2; 3] (lists) and [|1; 2; 3|] (arrays).
  • For lists and arrays and seqs, you can use the comprehension syntax for .. in .. do .. yield.

Usage examples

  1. // using list initializer
  2. let listInit1 = List.init 5 (fun i-> i*i)
  3. // val listInit1 : int list = [0; 1; 4; 9; 16]
  5. // using list comprehension
  6. let listInit2 = [for i in [1..5] do yield i*i]
  7. // val listInit2 : int list = [1; 4; 9; 16; 25]
  9. // literal 
  10. let listInit3 = [1; 4; 9; 16; 25]
  11. // val listInit3 : int list = [1; 4; 9; 16; 25]
  13. let arrayInit3 = [|1; 4; 9; 16; 25|]
  14. // val arrayInit3 : int [] = [|1; 4; 9; 16; 25|]

Literal syntax allows for an increment as well:

  1. // literal with +2 increment
  2. let listOdd= [1..2..10]
  3. // val listOdd : int list = [1; 3; 5; 7; 9]

The comprehension syntax is even more flexible because you can yield more than once:

  1. // using list comprehension
  2. let listFunny = [
  3.     for i in [2..3] do 
  4.         yield i
  5.         yield i*i
  6.         yield i*i*i
  7.         ]
  8. // val listFunny : int list = [2; 4; 8; 3; 9; 27]

and it can also be used as a quick and dirty inline filter:

  1. let primesUpTo n = 
  2.    let rec sieve l  = 
  3.       match l with 
  4.       | [] -> []
  5.       | p::xs -> 
  6.             p :: sieve [for x in xs do if (x % p) > 0 then yield x]
  7.    [2..n] |> sieve 
  9. primesUpTo 20
  10. // [2; 3; 5; 7; 11; 13; 17; 19]

Two other tricks:

  • You can use yield! to return a list rather than a single value
  • You can also use recursion

Here is an example of both tricks being used to count up to 10 by twos:

  1. let rec listCounter n = [
  2.     if n <= 10 then
  3.         yield n
  4.         yield! listCounter (n+2)
  5.     ]
  7. listCounter 3
  8. // val it : int list = [3; 5; 7; 9]
  9. listCounter 4
  10. // val it : int list = [4; 6; 8; 10]

7. Creating a new infinite collection

If you want an infinite list, you have to use a seq rather than a list or array.

  • initInfinite : initializer:(int -> 'T) -> seq<'T>.
    Generates a new sequence which, when iterated, will return successive elements by calling the given function.
  • You can also use a seq comprehension with a recursive loop to generate an infinite sequence.

Usage examples

  1. // generator version
  2. let seqOfSquares = Seq.initInfinite (fun i -> i*i)
  3. let firstTenSquares = seqOfSquares |> Seq.take 10
  5. firstTenSquares |> List.ofSeq // [0; 1; 4; 9; 16; 25; 36; 49; 64; 81]
  7. // recursive version
  8. let seqOfSquares_v2 = 
  9.     let rec loop n = seq {
  10.         yield n * n
  11.         yield! loop (n+1)
  12.         }
  13.     loop 1
  14. let firstTenSquares_v2 = seqOfSquares_v2 |> Seq.take 10

8. Creating a new collection of indefinite size

Sometimes you don’t know how big the collection will be in advance. In this case you need a function that will keep adding elements until it gets a signal to stop.
unfold is your friend here, and the “signal to stop” is whether you return a None (stop) or a Some (keep going).

Usage examples

This example reads from the console in a loop until an empty line is entered:

  1. let getInputFromConsole lineNo =
  2.     let text = System.Console.ReadLine()
  3.     if System.String.IsNullOrEmpty(text) then
  4.         None
  5.     else
  6.         // return value and new threaded state
  7.         // "text" will be in the generated sequence
  8.         Some (text,lineNo+1)
  10. let listUnfold = List.unfold getInputFromConsole 1

unfold requires that a state be threaded through the generator. You can ignore it (as in the ReadLine example above), or you can
use it to keep track of what you have done so far. For example, you can create a Fibonacci series generator using unfold:

  1. let fibonacciUnfolder max (f1,f2)  =
  2.     if f1 > max then
  3.         None
  4.     else
  5.         // return value and new threaded state
  6.         let fNext = f1 + f2
  7.         let newState = (f2,fNext)
  8.         // f1 will be in the generated sequence
  9.         Some (f1,newState)
  11. let fibonacci max = List.unfold (fibonacciUnfolder max) (1,1)
  12. fibonacci 100
  13. // int list = [1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89]

9. Working with one list

If you are working with one list and…

  • If you want to get an element at a known position, go to section 10
  • If you want to get one element by searching, go to section 11
  • If you want to get a subset of the collection, go to section 12
  • If you want to partition, chunk, or group a collection into smaller collections, go to section 13
  • If you want to aggregate or summarize the collection into a single value, go to section 14
  • If you want to change the order of the elements, go to section 15
  • If you want to test the elements in the collection, go to section 16
  • If you want to transform each element to something different, go to section 17
  • If you want to iterate over each element, go to section 18
  • If you want to thread state through an iteration, go to section 19
  • If you need to know the index of each element while you are iterating or mapping, go to section 20
  • If you want to transform the whole collection to a different collection type, go to section 21
  • If you want to change the behaviour of the collection as a whole, go to section 22
  • If you want to mutate the collection in place, go to section 27
  • If you want to use a lazy collection with an IDisposable, go to section 28

10. Getting an element at a known position

The following functions get a element in the collection by position:

But what if the collection is empty? Then head and last will fail with an exception (ArgumentException).

And if the index is not found in the collection? Then another exception again (ArgumentException for lists, IndexOutOfRangeException for arrays).

I would therefore recommend that you avoid these functions in general and use the tryXXX equivalents below:

Usage examples

  1. let head = [1;2;3] |> List.head
  2. // val head : int = 1
  4. let badHead : int = [] |> List.head
  5. // System.ArgumentException: The input list was empty.
  7. let goodHeadOpt = 
  8.     [1;2;3] |> List.tryHead 
  9. // val goodHeadOpt : int option = Some 1
  11. let badHeadOpt : int option = 
  12.     [] |> List.tryHead 
  13. // val badHeadOpt : int option = None    
  15. let goodItemOpt = 
  16.     [1;2;3] |> List.tryItem 2
  17. // val goodItemOpt : int option = Some 3
  19. let badItemOpt = 
  20.     [1;2;3] |> List.tryItem 99
  21. // val badItemOpt : int option = None

As noted, the item function should be avoided for lists. For example, if you want to process each item in a list, and you come from an imperative background,
you might write a loop with something like this:

  1. // Don't do this!
  2. let helloBad = 
  3.     let list = ["a";"b";"c"]
  4.     let listSize = List.length list
  5.     [ for i in [0..listSize-1] do
  6.         let element = list |> List.item i
  7.         yield "hello " + element 
  8.     ]
  9. // val helloBad : string list = ["hello a"; "hello b"; "hello c"]

Don’t do that! Use something like map instead. It’s both more concise and more efficient:

  1. let helloGood = 
  2.     let list = ["a";"b";"c"]
  3.     list |> List.map (fun element -> "hello " + element)
  4. // val helloGood : string list = ["hello a"; "hello b"; "hello c"]

11. Getting an element by searching

You can search for an element or its index using find and findIndex:

And you can also search backwards:

But what if the item cannot be found? Then these will fail with an exception (KeyNotFoundException).

I would therefore recommend that, as with head and item, you avoid these functions in general and use the tryXXX equivalents below:

If you are doing a map before a find you can often combine the two steps into a single one using pick (or better, tryPick). See below for a usage example.

Usage examples

  1. let listOfTuples = [ (1,"a"); (2,"b"); (3,"b"); (4,"a"); ]
  3. listOfTuples |> List.find ( fun (x,y) -> y = "b")
  4. // (2, "b")
  6. listOfTuples |> List.findBack ( fun (x,y) -> y = "b")
  7. // (3, "b")
  9. listOfTuples |> List.findIndex ( fun (x,y) -> y = "b")
  10. // 1
  12. listOfTuples |> List.findIndexBack ( fun (x,y) -> y = "b")
  13. // 2
  15. listOfTuples |> List.find ( fun (x,y) -> y = "c")
  16. // KeyNotFoundException

With pick, rather than returning a bool, you return an option:

  1. listOfTuples |> List.pick ( fun (x,y) -> if y = "b" then Some (x,y) else None)
  2. // (2, "b")

Pick vs. Find

That ‘pick’ function might seem unnecessary, but it is useful when dealing with functions that return options.

For example, say that there is a function tryInt that parses a string and returns Some int if the string is a valid int, otherwise None.

  1. // string -> int option
  2. let tryInt str = 
  3.     match System.Int32.TryParse(str) with
  4.     | true, i -> Some i
  5.     | false, _ -> None

And now say that we want to find the first valid int in a list. The crude way would be:

  • map the list using tryInt
  • find the first one that is a Some using find
  • get the value from inside the option using Option.get

The code might look something like this:

  1. let firstValidNumber = 
  2.     ["a";"2";"three"]
  3.     // map the input
  4.     |> List.map tryInt 
  5.     // find the first Some
  6.     |> List.find (fun opt -> opt.IsSome)
  7.     // get the data from the option
  8.     |> Option.get
  9. // val firstValidNumber : int = 2

But pick will do all these steps at once! So the code becomes much simpler:

  1. let firstValidNumber = 
  2.     ["a";"2";"three"]
  3.     |> List.pick tryInt

If you want to return many elements in the same way as pick, consider using choose (see section 12).

12. Getting a subset of elements from a collection

The previous section was about getting one element. How can you get more than one element? Well you’re in luck! There’s lots of functions to choose from.

To extract elements from the front, use one of these:

To extract elements from the rear, use one of these:

To extract other subsets of elements, use one of these:

To reduce the list to distinct elements, use one of these:

Usage examples

Taking elements from the front:

  1. [1..10] |> List.take 3    
  2. // [1; 2; 3]
  4. [1..10] |> List.takeWhile (fun i -> i < 3)    
  5. // [1; 2]
  7. [1..10] |> List.truncate 4
  8. // [1; 2; 3; 4]
  10. [1..2] |> List.take 3    
  11. // System.InvalidOperationException: The input sequence has an insufficient number of elements.
  13. [1..2] |> List.takeWhile (fun i -> i < 3)  
  14. // [1; 2]
  16. [1..2] |> List.truncate 4
  17. // [1; 2]   // no error!

Taking elements from the rear:

  1. [1..10] |> List.skip 3    
  2. // [4; 5; 6; 7; 8; 9; 10]
  4. [1..10] |> List.skipWhile (fun i -> i < 3)    
  5. // [3; 4; 5; 6; 7; 8; 9; 10]
  7. [1..10] |> List.tail
  8. // [2; 3; 4; 5; 6; 7; 8; 9; 10]
  10. [1..2] |> List.skip 3    
  11. // System.ArgumentException: The index is outside the legal range.
  13. [1..2] |> List.skipWhile (fun i -> i < 3)  
  14. // []
  16. [1] |> List.tail |> List.tail
  17. // System.ArgumentException: The input list was empty.

To extract other subsets of elements:

  1. [1..10] |> List.filter (fun i -> i%2 = 0) // even
  2. // [2; 4; 6; 8; 10]
  4. [1..10] |> List.where (fun i -> i%2 = 0) // even
  5. // [2; 4; 6; 8; 10]
  7. [1..10] |> List.except [3;4;5]
  8. // [1; 2; 6; 7; 8; 9; 10]

To extract a slice:

  1. Array.sub [|1..10|] 3 5
  2. // [|4; 5; 6; 7; 8|]
  4. [1..10].[3..5] 
  5. // [4; 5; 6]
  7. [1..10].[3..] 
  8. // [4; 5; 6; 7; 8; 9; 10]
  10. [1..10].[..5] 
  11. // [1; 2; 3; 4; 5; 6]

Note that slicing on lists can be slow, because they are not random access. Slicing on arrays is fast however.

To extract the distinct elements:

  1. [1;1;1;2;3;3] |> List.distinct
  2. // [1; 2; 3]
  4. [ (1,"a"); (1,"b"); (1,"c"); (2,"d")] |> List.distinctBy fst
  5. // [(1, "a"); (2, "d")]

Choose vs. Filter

As with pick, the choose function might seem awkward, but it is useful when dealing with functions that return options.

In fact, choose is to filter as pick is to find, Rather than using a boolean filter, the signal is Some vs. None.

As before, say that there is a function tryInt that parses a string and returns Some int if the string is a valid int, otherwise None.

  1. // string -> int option
  2. let tryInt str = 
  3.     match System.Int32.TryParse(str) with
  4.     | true, i -> Some i
  5.     | false, _ -> None

And now say that we want to find all the valid ints in a list. The crude way would be:

  • map the list using tryInt
  • filter to only include the ones that are Some
  • get the value from inside each option using Option.get

The code might look something like this:

  1. let allValidNumbers = 
  2.     ["a";"2";"three"; "4"]
  3.     // map the input
  4.     |> List.map tryInt 
  5.     // include only the "Some"
  6.     |> List.filter (fun opt -> opt.IsSome)
  7.     // get the data from each option
  8.     |> List.map Option.get
  9. // val allValidNumbers : int list = [2; 4]

But choose will do all these steps at once! So the code becomes much simpler:

  1. let allValidNumbers = 
  2.     ["a";"2";"three"; "4"]
  3.     |> List.choose tryInt

If you already have a list of options, you can filter and return the “Some” in one step by passing id into choose:

  1. let reduceOptions = 
  2.     [None; Some 1; None; Some 2]
  3.     |> List.choose id
  4. // val reduceOptions : int list = [1; 2]

If you want to return the first element in the same way as choose, consider using pick (see section 11).

If you want to do a similar action as choose but for other wrapper types (such as a Success/Failure result), there is a discussion here.

13. Partitioning, chunking and grouping

There are lots of different ways to split a collection! Have a look at the usage examples to see the differences:

Usage examples

  1. [1..10] |> List.chunkBySize 3
  2. // [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]; [10]]  
  3. // note that the last chunk has one element
  5. [1..10] |> List.splitInto 3
  6. // [[1; 2; 3; 4]; [5; 6; 7]; [8; 9; 10]]
  7. // note that the first chunk has four elements
  9. ['a'..'i'] |> List.splitAt 3
  10. // (['a'; 'b'; 'c'], ['d'; 'e'; 'f'; 'g'; 'h'; 'i'])
  12. ['a'..'e'] |> List.pairwise
  13. // [('a', 'b'); ('b', 'c'); ('c', 'd'); ('d', 'e')]
  15. ['a'..'e'] |> List.windowed 3
  16. // [['a'; 'b'; 'c']; ['b'; 'c'; 'd']; ['c'; 'd'; 'e']]
  18. let isEven i = (i%2 = 0)
  19. [1..10] |> List.partition isEven 
  20. // ([2; 4; 6; 8; 10], [1; 3; 5; 7; 9])
  22. let firstLetter (str:string) = str.[0]
  23. ["apple"; "alice"; "bob"; "carrot"] |> List.groupBy firstLetter 
  24. // [('a', ["apple"; "alice"]); ('b', ["bob"]); ('c', ["carrot"])]

All the functions other than splitAt and pairwise handle edge cases gracefully:

  1. [1] |> List.chunkBySize 3
  2. // [[1]]
  4. [1] |> List.splitInto 3
  5. // [[1]]
  7. ['a'; 'b'] |> List.splitAt 3
  8. // InvalidOperationException: The input sequence has an insufficient number of elements.
  10. ['a'] |> List.pairwise
  11. // InvalidOperationException: The input sequence has an insufficient number of elements.
  13. ['a'] |> List.windowed 3
  14. // []
  16. [1] |> List.partition isEven 
  17. // ([], [1])
  19. [] |> List.groupBy firstLetter 
  20. //  []

14. Aggregating or summarizing a collection

The most generic way to aggregate the elements in a collection is to use reduce:

and there are specific versions of reduce for frequently used aggregations:

Finally there are some counting functions:

Usage examples

reduce is a variant of fold without an initial state — see section 19 for more on fold. One way to think of it is just inserting a operator between
each element.

  1. ["a";"b";"c"] |> List.reduce (+)     
  2. // "abc"

is the same as 

  1. "a" + "b" + "c"

Here’s another example:

  1. [2;3;4] |> List.reduce (*)     
  2. // is same as
  3. 2 * 3 * 4
  4. // Result is 24

Some ways of combining elements depend on the order of combining, and so there are two variants of “reduce”:

  • reduce moves forward through the list.
  • reduceBack, not surprisingly, moves backwards through the list.

Here’s a demonstration of the difference. First reduce:

  1. [1;2;3;4] |> List.reduce (fun state x -> (state)*10 + x)
  3. // built up from                // state at each step
  4. 1                               // 1
  5. (1)*10 + 2                      // 12 
  6. ((1)*10 + 2)*10 + 3             // 123 
  7. (((1)*10 + 2)*10 + 3)*10 + 4    // 1234
  9. // Final result is 1234

Using the same combining function with reduceBack produces a different result! It looks like this:

  1. [1;2;3;4] |> List.reduceBack (fun x state -> x + 10*(state))
  3. // built up from                // state at each step
  4. 4                               // 4
  5. 3 + 10*(4)                      // 43  
  6. 2 + 10*(3 + 10*(4))             // 432  
  7. 1 + 10*(2 + 10*(3 + 10*(4)))    // 4321  
  9. // Final result is 4321

Again, see section 19 for a more detailed discussion of the related functions fold and foldBack.

The other aggregation functions are much more straightforward.

  1. type Suit = Club | Diamond | Spade | Heart 
  2. type Rank = Two | Three | King | Ace
  3. let cards = [ (Club,King); (Diamond,Ace); (Spade,Two); (Heart,Three); ]
  5. cards |> List.max        // (Heart, Three)
  6. cards |> List.maxBy snd  // (Diamond, Ace)
  7. cards |> List.min        // (Club, King)
  8. cards |> List.minBy snd  // (Spade, Two)
  10. [1..10] |> List.sum
  11. // 55
  13. [ (1,"a"); (2,"b") ] |> List.sumBy fst
  14. // 3
  16. [1..10] |> List.average
  17. // The type 'int' does not support the operator 'DivideByInt'
  19. [1..10] |> List.averageBy float
  20. // 5.5
  22. [ (1,"a"); (2,"b") ] |> List.averageBy (fst >> float)
  23. // 1.5
  25. [1..10] |> List.length
  26. // 10
  28. [ ("a","A"); ("b","B"); ("a","C") ]  |> List.countBy fst
  29. // [("a", 2); ("b", 1)]
  31. [ ("a","A"); ("b","B"); ("a","C") ]  |> List.countBy snd
  32. // [("A", 1); ("B", 1); ("C", 1)]

Most of the aggregation functions do not like empty lists! You might consider using one of the fold functions to be safe — see section 19.

  1. let emptyListOfInts : int list = []
  3. emptyListOfInts |> List.reduce (+)     
  4. // ArgumentException: The input list was empty.
  6. emptyListOfInts |> List.max
  7. // ArgumentException: The input sequence was empty.
  9. emptyListOfInts |> List.min
  10. // ArgumentException: The input sequence was empty.
  12. emptyListOfInts |> List.sum      
  13. // 0
  15. emptyListOfInts |> List.averageBy float
  16. // ArgumentException: The input sequence was empty.
  18. let emptyListOfTuples : (int*int) list = []
  19. emptyListOfTuples |> List.countBy fst
  20. // (int * int) list = []

15. Changing the order of the elements

You can change the order of the elements using reversing, sorting and permuting. All of the following return new collections:

And there are also some array-only functions that sort in place:

Usage examples

  1. [1..5] |> List.rev
  2. // [5; 4; 3; 2; 1]
  4. [2;4;1;3;5] |> List.sort
  5. // [1; 2; 3; 4; 5]
  7. [2;4;1;3;5] |> List.sortDescending
  8. // [5; 4; 3; 2; 1]
  10. [ ("b","2"); ("a","3"); ("c","1") ]  |> List.sortBy fst
  11. // [("a", "3"); ("b", "2"); ("c", "1")]
  13. [ ("b","2"); ("a","3"); ("c","1") ]  |> List.sortBy snd
  14. // [("c", "1"); ("b", "2"); ("a", "3")]
  16. // example of a comparer
  17. let tupleComparer tuple1 tuple2  =
  18.     if tuple1 < tuple2 then 
  19.         -1 
  20.     elif tuple1 > tuple2 then 
  21.         1 
  22.     else
  23.         0
  25. [ ("b","2"); ("a","3"); ("c","1") ]  |> List.sortWith tupleComparer
  26. // [("a", "3"); ("b", "2"); ("c", "1")]
  28. [1..10] |> List.permute (fun i -> (i + 3) % 10)
  29. // [8; 9; 10; 1; 2; 3; 4; 5; 6; 7]
  31. [1..10] |> List.permute (fun i -> 9 - i)
  32. // [10; 9; 8; 7; 6; 5; 4; 3; 2; 1]

16. Testing the elements of a collection

These set of functions all return true or false.

Usage examples

  1. [1..10] |> List.contains 5
  2. // true
  4. [1..10] |> List.contains 42
  5. // false
  7. [1..10] |> List.exists (fun i -> i > 3 && i < 5)
  8. // true
  10. [1..10] |> List.exists (fun i -> i > 5 && i < 3)
  11. // false
  13. [1..10] |> List.forall (fun i -> i > 0)
  14. // true
  16. [1..10] |> List.forall (fun i -> i > 5)
  17. // false
  19. [1..10] |> List.isEmpty
  20. // false

17. Transforming each element to something different

I sometimes like to think of functional programming as “transformation-oriented programming”, and map (aka Select in LINQ) is one of the most fundamental ingredients for this approach.
In fact, I have devoted a whole series to it here.

Sometimes each element maps to a list, and you want to flatten out all the lists. For this case, use collect (aka SelectMany in LINQ).

Other transformation functions include:

Usage examples

Here are some examples of using map in the conventional way, as a function that accepts a list and a mapping function and returns a new transformed list: 

  1. let add1 x = x + 1
  3. // map as a list transformer
  4. [1..5] |> List.map add1
  5. // [2; 3; 4; 5; 6]
  7. // the list being mapped over can contain anything!
  8. let times2 x = x * 2
  9. [ add1; times2] |> List.map (fun f -> f 5)
  10. // [6; 10]

You can also think of map as a function transformer. It turns an element-to-element function into a list-to-list function.

  1. let add1ToEachElement = List.map add1
  2. // "add1ToEachElement" transforms lists to lists rather than ints to ints
  3. // val add1ToEachElement : (int list -> int list)
  5. // now use it
  6. [1..5] |> add1ToEachElement 
  7. // [2; 3; 4; 5; 6]

collect works to flatten lists. If you already have a list of lists, you can use collect with id to flatten them.

  1. [2..5] |> List.collect (fun x -> [x; x*x; x*x*x] )
  2. // [2; 4; 8; 3; 9; 27; 4; 16; 64; 5; 25; 125]
  4. // using "id" with collect
  5. let list1 = [1..3]
  6. let list2 = [4..6]
  7. [list1; list2] |> List.collect id
  8. // [1; 2; 3; 4; 5; 6]

Seq.cast

Finally, Seq.cast is useful when working with older parts of the BCL that have specialized collection classes rather than generics.

For example, the Regex library has this problem, and so the code below won’t compile because MatchCollection is not an IEnumerable<T>

  1. open System.Text.RegularExpressions
  3. let matches = 
  4.     let pattern = "\d\d\d"
  5.     let matchCollection = Regex.Matches("123 456 789",pattern)
  6.     matchCollection
  7.     |> Seq.map (fun m -> m.Value)     // ERROR
  8.     // ERROR: The type 'MatchCollection' is not compatible with the type 'seq<'a>'
  9.     |> Seq.toList

The fix is to cast MatchCollection to a Seq<Match> and then the code will work nicely:

  1. let matches = 
  2.     let pattern = "\d\d\d"
  3.     let matchCollection = Regex.Matches("123 456 789",pattern)
  4.     matchCollection
  5.     |> Seq.cast<Match> 
  6.     |> Seq.map (fun m -> m.Value)
  7.     |> Seq.toList
  8. // output = ["123"; "456"; "789"]

18. Iterating over each element

Normally, when processing a collection, we transform each element to a new value using map. But occasionally we need to process all the elements with a function which doesn’t
produce a useful value (a “unit function”).

Usage examples

The most common examples of unit functions are all about side-effects: printing to the console, updating a database, putting a message on a queue, etc.
For the examples below, I will just use printfn as my unit function.

  1. [1..3] |> List.iter (fun i -> printfn "i is %i" i)
  2. (*
  3. i is 1
  4. i is 2
  5. i is 3
  6. *)
  8. // or using partial application
  9. [1..3] |> List.iter (printfn "i is %i")
  11. // or using a for loop
  12. for i = 1 to 3 do
  13.     printfn "i is %i" i
  15. // or using a for-in loop
  16. for i in [1..3] do
  17.     printfn "i is %i" i

As noted above, the expression inside an iter or for-loop must return unit. In the following examples, we try to add 1 to the element, and get a compiler error:

  1. [1..3] |> List.iter (fun i -> i + 1)
  2. //                               ~~~
  3. // ERROR error FS0001: The type 'unit' does not match the type 'int'
  5. // a for-loop expression *must* return unit
  6. for i in [1..3] do
  7.      i + 1  // ERROR
  8.      // This expression should have type 'unit', 
  9.      // but has type 'int'. Use 'ignore' ...

If you are sure that this is not a logic bug in your code, and you want to get rid of this error, you can pipe the results into ignore:

  1. [1..3] |> List.iter (fun i -> i + 1 |> ignore)
  3. for i in [1..3] do
  4.      i + 1 |> ignore

19. Threading state through an iteration

The fold function is the most basic and powerful function in the collection arsenal. All other functions (other than generators like unfold) can be written in terms of it. See the examples below.

The fold function is often called “fold left” and foldBack is often called “fold right”.

The scan function is like fold but returns the intermediate results and thus can be used to trace or monitor the iteration.

Just like the fold twins, scan is often called “scan left” and scanBack is often called “scan right”.

Finally, mapFold combines map and fold into one awesome superpower. More complicated than using map and fold separately but also more efficient.

fold examples

One way of thinking about fold is that it is like reduce but with an extra parameter for the initial state:

  1. ["a";"b";"c"] |> List.fold (+) "hello: "    
  2. // "hello: abc"
  3. // "hello: " + "a" + "b" + "c"
  5. [1;2;3] |> List.fold (+) 10    
  6. // 16
  7. // 10 + 1 + 2 + 3

As with reduce, fold and foldBack can give very different answers.

  1. [1;2;3;4] |> List.fold (fun state x -> (state)*10 + x) 0
  2.                                 // state at each step
  3. 1                               // 1
  4. (1)*10 + 2                      // 12 
  5. ((1)*10 + 2)*10 + 3             // 123 
  6. (((1)*10 + 2)*10 + 3)*10 + 4    // 1234
  7. // Final result is 1234

And here’s the foldBack version:

  1. List.foldBack (fun x state -> x + 10*(state)) [1;2;3;4] 0
  2.                                 // state at each step  
  3. 4                               // 4
  4. 3 + 10*(4)                      // 43  
  5. 2 + 10*(3 + 10*(4))             // 432  
  6. 1 + 10*(2 + 10*(3 + 10*(4)))    // 4321  
  7. // Final result is 4321

Note that foldBack has a different parameter order to fold: the list is second last, and the initial state is last, which means that piping is not as convenient.

Recursing vs iterating

It’s easy to get confused between fold vs. foldBack. I find it helpful to think of fold as being about iteration while foldBack is about recursion.

Let’s say we want to calculate the sum of a list. The iterative way would be to use a for-loop.
You start with a (mutable) accumulator and thread it through each iteration, updating it as you go.

  1. let iterativeSum list = 
  2.     let mutable total = 0
  3.     for e in list do
  4.         total <- total + e
  5.     total // return sum

On the other hand, the recursive approach says that
if the list has a head and tail, calculate the sum of the tail (a smaller list) first, and then add the head to it.

Each time the tail gets smaller and smaller until it is empty, at which point you’re done.

  1. let rec recursiveSum list = 
  2.     match list with
  3.     | [] -> 
  4.         0
  5.     | head::tail -> 
  6.         head + (recursiveSum tail)

Which approach is better?

For aggregation, the iterative way is (fold) often easiest to understand.
But for things like constructing new lists, the recursive way is (foldBack) is easier to understand.

For example, if we were going to going to create a function from scratch that turned each element into the corresponding string,
we might write something like this:

  1. let rec mapToString list = 
  2.     match list with
  3.     | [] -> 
  4.         []
  5.     | head::tail -> 
  6.         head.ToString() :: (mapToString tail)
  8. [1..3] |> mapToString 
  9. // ["1"; "2"; "3"]

Using foldBack we can transfer that same logic “as is”:

  • action for empty list = []
  • action for non-empty list = head.ToString() :: state

Here is the resulting function:

  1. let foldToString list = 
  2.     let folder head state = 
  3.         head.ToString() :: state
  4.     List.foldBack folder list []
  6. [1..3] |> foldToString 
  7. // ["1"; "2"; "3"]

On the other hand, a big advantage of fold is that it is easier to use “inline” because it plays better with piping.

Luckily, you can use fold (for list construction at least) just like foldBack as long as you reverse the list at the end.

  1. // inline version of "foldToString"
  2. [1..3] 
  3. |> List.fold (fun state head -> head.ToString() :: state) []
  4. |> List.rev
  5. // ["1"; "2"; "3"]

Using fold to implement other functions

As I mentioned above, fold is the core function for operating on lists and can emulate most other functions,
although perhaps not as efficiently as a custom implementation.

For example, here is map implemented using fold:

  1. /// map a function "f" over all elements
  2. let myMap f list = 
  3.     // helper function
  4.     let folder state head =
  5.         f head :: state
  7.     // main flow
  8.     list
  9.     |> List.fold folder []
  10.     |> List.rev
  12. [1..3] |> myMap (fun x -> x + 2)
  13. // [3; 4; 5]

And here is filter implemented using fold:

  1. /// return a new list of elements for which "pred" is true
  2. let myFilter pred list = 
  3.     // helper function
  4.     let folder state head =
  5.         if pred head then 
  6.             head :: state
  7.         else
  8.             state
  10.     // main flow
  11.     list
  12.     |> List.fold folder []
  13.     |> List.rev
  15. let isOdd n = (n%2=1)
  16. [1..5] |> myFilter isOdd 
  17. // [1; 3; 5]

And of course, you can emulate the other functions in a similar way.

scan examples

Earlier, I showed an example of the intermediate steps of fold:

  1. [1;2;3;4] |> List.fold (fun state x -> (state)*10 + x) 0
  2.                                 // state at each step
  3. 1                               // 1
  4. (1)*10 + 2                      // 12 
  5. ((1)*10 + 2)*10 + 3             // 123 
  6. (((1)*10 + 2)*10 + 3)*10 + 4    // 1234
  7. // Final result is 1234

For that example, I had to manually calculate the intermediate states,

Well, if I had used scan, I would have got those intermediate states for free!

  1. [1;2;3;4] |> List.scan (fun state x -> (state)*10 + x) 0
  2. // accumulates from left ===> [0; 1; 12; 123; 1234]

scanBack works the same way, but backwards of course:

  1. List.scanBack (fun x state -> (state)*10 + x) [1;2;3;4] 0
  2. // [4321; 432; 43; 4; 0]  <=== accumulates from right

Just as with foldBack the parameter order for “scan right” is inverted compared with “scan left”.

Truncating a string with scan

Here’s an example where scan is useful. Say that you have a news site, and you need to make sure headlines fit into 50 chars.

You could just truncate the string at 50, but that would look ugly. Instead you want to have the truncation end at a word boundary.

Here’s one way of doing it using scan:

  • Split the headline into words.
  • Use scan to concat the words back together, generating a list of fragments, each with an extra word added.
  • Get the longest fragment under 50 chars.
  1. // start by splitting the text into words
  2. let text = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor."
  3. let words = text.Split(' ')
  4. // [|"Lorem"; "ipsum"; "dolor"; "sit"; ... ]
  6. // accumulate a series of fragments
  7. let fragments = words |> Seq.scan (fun frag word -> frag + " " + word) ""
  8. (*
  9. " Lorem" 
  10. " Lorem ipsum" 
  11. " Lorem ipsum dolor"
  12. " Lorem ipsum dolor sit" 
  13. " Lorem ipsum dolor sit amet,"
  14. etc
  15. *)
  17. // get the longest fragment under 50
  18. let longestFragUnder50 = 
  19.     fragments 
  20.     |> Seq.takeWhile (fun s -> s.Length <= 50) 
  21.     |> Seq.last 
  23. // trim off the first blank
  24. let longestFragUnder50Trimmed = 
  25.     longestFragUnder50 |> (fun s -> s.[1..])
  27. // The result is:
  28. //   "Lorem ipsum dolor sit amet, consectetur"

Note that I’m using Seq.scan rather than Array.scan. This does a lazy scan and avoids having to create fragments that are not needed.

Finally, here is the complete logic as a utility function:

  1. // the whole thing as a function
  2. let truncText max (text:string) = 
  3.     if text.Length <= max then
  4.         text
  5.     else
  6.         text.Split(' ')
  7.         |> Seq.scan (fun frag word -> frag + " " + word) ""
  8.         |> Seq.takeWhile (fun s -> s.Length <= max-3) 
  9.         |> Seq.last 
  10.         |> (fun s -> s.[1..] + "...")
  12. "a small headline" |> truncText 50
  13. // "a small headline"
  15. text |> truncText 50
  16. // "Lorem ipsum dolor sit amet, consectetur..."

Yes, I know that there is a more efficient implementation than this, but I hope that this little example shows off the power of scan.

mapFold examples

The mapFold function can do a map and a fold in one step, which can be convenient on occasion.

Here’s an example of combining an addition and a sum in one step using mapFold:

  1. let add1 x = x + 1
  3. // add1 using map
  4. [1..5] |> List.map (add1)   
  5. // Result => [2; 3; 4; 5; 6]
  7. // sum using fold
  8. [1..5] |> List.fold (fun state x -> state + x) 0   
  9. // Result => 15
  11. // map and sum using mapFold
  12. [1..5] |> List.mapFold (fun state x -> add1 x, (state + x)) 0   
  13. // Result => ([2; 3; 4; 5; 6], 15)

20. Working with the index of each element

Often, you need the index of the element as you do an iteration. You could use a mutable counter, but why not sit back and let the library do the work for you?

Usage examples

  1. ['a'..'c'] |> List.mapi (fun index ch -> sprintf "the %ith element is '%c'" index ch)
  2. // ["the 0th element is 'a'"; "the 1th element is 'b'"; "the 2th element is 'c'"]
  4. // with partial application
  5. ['a'..'c'] |> List.mapi (sprintf "the %ith element is '%c'")
  6. // ["the 0th element is 'a'"; "the 1th element is 'b'"; "the 2th element is 'c'"]
  8. ['a'..'c'] |> List.iteri (printfn "the %ith element is '%c'")
  9. (*
  10. the 0th element is 'a'
  11. the 1th element is 'b'
  12. the 2th element is 'c'
  13. *)

indexed generates a tuple with the index — a shortcut for a specific use of mapi:

  1. ['a'..'c'] |> List.mapi (fun index ch -> (index, ch) )
  2. // [(0, 'a'); (1, 'b'); (2, 'c')]
  4. // "indexed" is a shorter version of above
  5. ['a'..'c'] |> List.indexed
  6. // [(0, 'a'); (1, 'b'); (2, 'c')]

21. Transforming the whole collection to a different collection type

You often need to convert from one kind of collection to another. These functions do this.

The ofXXX functions are used to convert from XXX to the module type. For example, List.ofArray will turn an array into a list.

The toXXX are used to convert from the module type to the type XXX. For example, List.toArray will turn an list into an array.

Usage examples

  1. [1..5] |> List.toArray      // [|1; 2; 3; 4; 5|]
  2. [1..5] |> Array.ofList      // [|1; 2; 3; 4; 5|]
  3. // etc

Using sequences with disposables

One important use of these conversion functions is to convert a lazy enumeration (seq) to a fully evaluated collection such as list. This is particularly
important when there is a disposable resource involved, such as file handle or database connection. If the sequence is not converted into a list
you may encounter errors accessing the elements. See section 28 for more.

22. Changing the behavior of the collection as a whole

There are some special functions (for Seq only) that change the behavior of the collection as a whole.

  • (Seq only) cache: source:seq<'T> -> seq<'T>.
    Returns a sequence that corresponds to a cached version of the input sequence. This result sequence will have the same elements as the input sequence. The result
    can be enumerated multiple times. The input sequence will be enumerated at most once and only as far as is necessary.
  • (Seq only) readonly : source:seq<'T> -> seq<'T>.
    Builds a new sequence object that delegates to the given sequence object. This ensures the original sequence cannot be rediscovered and mutated by a type cast.
  • (Seq only) delay : generator:(unit -> seq<'T>) -> seq<'T>.
    Returns a sequence that is built from the given delayed specification of a sequence.

cache example

Here’s an example of cache in use:

  1. let uncachedSeq = seq {
  2.     for i = 1 to 3 do
  3.         printfn "Calculating %i" i
  4.         yield i
  5.     }
  7. // iterate twice    
  8. uncachedSeq |> Seq.iter ignore
  9. uncachedSeq |> Seq.iter ignore

The result of iterating over the sequence twice is as you would expect:

  1. Calculating 1
  2. Calculating 2
  3. Calculating 3
  4. Calculating 1
  5. Calculating 2
  6. Calculating 3

But if we cache the sequence…

  1. let cachedSeq = uncachedSeq |> Seq.cache
  3. // iterate twice    
  4. cachedSeq |> Seq.iter ignore
  5. cachedSeq |> Seq.iter ignore

… then each item is only printed once:

  1. Calculating 1
  2. Calculating 2
  3. Calculating 3

readonly example

Here’s an example of readonly being used to hide the underlying type of the sequence:

  1. // print the underlying type of the sequence
  2. let printUnderlyingType (s:seq<_>) =
  3.     let typeName = s.GetType().Name 
  4.     printfn "%s" typeName 
  6. [|1;2;3|] |> printUnderlyingType 
  7. // Int32[]
  9. [|1;2;3|] |> Seq.readonly |> printUnderlyingType 
  10. // mkSeq@589   // a temporary type

delay example

Here’s an example of delay.

  1. let makeNumbers max =
  2.     [ for i = 1 to max do
  3.         printfn "Evaluating %d." i
  4.         yield i ]
  6. let eagerList = 
  7.     printfn "Started creating eagerList" 
  8.     let list = makeNumbers 5
  9.     printfn "Finished creating eagerList" 
  10.     list
  12. let delayedSeq = 
  13.     printfn "Started creating delayedSeq" 
  14.     let list = Seq.delay (fun () -> makeNumbers 5 |> Seq.ofList)
  15.     printfn "Finished creating delayedSeq" 
  16.     list

If we run the code above, we find that just by creating eagerList, we print all the “Evaluating” messages. But creating delayedSeq does not trigger the list iteration.

  1. Started creating eagerList
  2. Evaluating 1.
  3. Evaluating 2.
  4. Evaluating 3.
  5. Evaluating 4.
  6. Evaluating 5.
  7. Finished creating eagerList
  9. Started creating delayedSeq
  10. Finished creating delayedSeq

Only when the sequence is iterated over does the list creation happen:

  1. eagerList |> Seq.take 3  // list already created
  2. delayedSeq |> Seq.take 3 // list creation triggered

An alternative to using delay is just to embed the list in a seq like this:

  1. let embeddedList = seq {
  2.     printfn "Started creating embeddedList" 
  3.     yield! makeNumbers 5 
  4.     printfn "Finished creating embeddedList" 
  5.     }

As with delayedSeq, the makeNumbers function will not be called until the sequence is iterated over.

23. Working with two lists

If you have two lists, there are analogues of most of the common functions like map and fold.

Usage examples

These functions are straightforward to use:

  1. let intList1 = [2;3;4]
  2. let intList2 = [5;6;7]
  4. List.map2 (fun i1 i2 -> i1 + i2) intList1 intList2 
  5. //  [7; 9; 11]
  7. // TIP use the ||> operator to pipe a tuple as two arguments
  8. (intList1,intList2) ||> List.map2 (fun i1 i2 -> i1 + i2) 
  9. //  [7; 9; 11]
  11. (intList1,intList2) ||> List.mapi2 (fun index i1 i2 -> index,i1 + i2) 
  12.  // [(0, 7); (1, 9); (2, 11)]
  14. (intList1,intList2) ||> List.iter2 (printf "i1=%i i2=%i; ") 
  15. // i1=2 i2=5; i1=3 i2=6; i1=4 i2=7;
  17. (intList1,intList2) ||> List.iteri2 (printf "index=%i i1=%i i2=%i; ") 
  18. // index=0 i1=2 i2=5; index=1 i1=3 i2=6; index=2 i1=4 i2=7;
  20. (intList1,intList2) ||> List.forall2 (fun i1 i2 -> i1 < i2)  
  21. // true
  23. (intList1,intList2) ||> List.exists2 (fun i1 i2 -> i1+10 > i2)  
  24. // true
  26. (intList1,intList2) ||> List.fold2 (fun state i1 i2 -> (10*state) + i1 + i2) 0 
  27. // 801 = 234 + 567
  29. List.foldBack2 (fun i1 i2 state -> i1 + i2 + (10*state)) intList1 intList2 0 
  30. // 1197 = 432 + 765
  32. (intList1,intList2) ||> List.compareWith (fun i1 i2 -> i1.CompareTo(i2))  
  33. // -1
  35. (intList1,intList2) ||> List.append
  36. // [2; 3; 4; 5; 6; 7]
  38. [intList1;intList2] |> List.concat
  39. // [2; 3; 4; 5; 6; 7]
  41. (intList1,intList2) ||> List.zip
  42. // [(2, 5); (3, 6); (4, 7)]

Need a function that’s not here?

By using fold2 and foldBack2 you can easily create your own functions. For example, some filter2 functions can be defined like this:

  1. /// Apply a function to each element in a pair
  2. /// If either result passes, include that pair in the result
  3. let filterOr2 filterPredicate list1 list2 =
  4.     let pass e = filterPredicate e 
  5.     let folder e1 e2 state =    
  6.         if (pass e1) || (pass e2) then
  7.             (e1,e2)::state
  8.         else
  9.             state
  10.     List.foldBack2 folder list1 list2 ([])
  12. /// Apply a function to each element in a pair
  13. /// Only if both results pass, include that pair in the result
  14. let filterAnd2 filterPredicate list1 list2 =
  15.     let pass e = filterPredicate e 
  16.     let folder e1 e2 state =     
  17.         if (pass e1) && (pass e2) then
  18.             (e1,e2)::state
  19.         else
  20.             state
  21.     List.foldBack2 folder list1 list2 []
  23. // test it
  24. let startsWithA (s:string) = (s.[0] = 'A')
  25. let strList1 = ["A1"; "A3"]
  26. let strList2 = ["A2"; "B1"]
  28. (strList1, strList2) ||> filterOr2 startsWithA 
  29. // [("A1", "A2"); ("A3", "B1")]
  30. (strList1, strList2) ||> filterAnd2 startsWithA 
  31. // [("A1", "A2")]

See also section 25.

24. Working with three lists

If you have three lists, you only have one built-in function available. But see section 25 for an example of how you can build your own three-list functions.

25. Working with more than three lists

If you are working with more than three lists, there are no built in functions for you.

If this happens infrequently, then you could just collapse the lists into a single tuple using zip2 and/or zip3 in succession, and then process that tuple using map.

Alternatively you can “lift” your function to the world of “zip lists” using applicatives. 

  1. let (<*>) fList xList = 
  2.     List.map2 (fun f x -> f x) fList xList 
  4. let (<!>) = List.map
  6. let addFourParams x y z w = 
  7.     x + y + z + w
  9. // lift "addFourParams" to List world and pass lists as parameters rather than ints
  10. addFourParams <!> [1;2;3] <*> [1;2;3] <*> [1;2;3] <*> [1;2;3] 
  11. // Result = [4; 8; 12]

If that seems like magic, see this series for a explanation of what this code is doing.

26. Combining and uncombining collections

Finally, there are a number of functions that combine and uncombine collections.

Usage examples

These functions are straightforward to use:

  1. List.append [1;2;3] [4;5;6]
  2. // [1; 2; 3; 4; 5; 6]
  4. [1;2;3] @ [4;5;6]
  5. // [1; 2; 3; 4; 5; 6]
  7. List.concat [ [1]; [2;3]; [4;5;6] ]
  8. // [1; 2; 3; 4; 5; 6]
  10. List.zip [1;2] [10;20] 
  11. // [(1, 10); (2, 20)]
  13. List.zip3 [1;2] [10;20] [100;200]
  14. // [(1, 10, 100); (2, 20, 200)]
  16. List.unzip [(1, 10); (2, 20)]
  17. // ([1; 2], [10; 20])
  19. List.unzip3 [(1, 10, 100); (2, 20, 200)]
  20. // ([1; 2], [10; 20], [100; 200])

Note that the zip functions require the lengths to be the same.

  1. List.zip [1;2] [10] 
  2. // ArgumentException: The lists had different lengths.

27. Other array-only functions

Arrays are mutable, and therefore have some functions that are not applicable to lists and sequences.

  • See the “sort in place” functions in section 15
  • Array.blit: source:'T[] -> sourceIndex:int -> target:'T[] -> targetIndex:int -> count:int -> unit.
    Reads a range of elements from the first array and write them into the second.
  • Array.copy: array:'T[] -> 'T[].
    Builds a new array that contains the elements of the given array.
  • Array.fill: target:'T[] -> targetIndex:int -> count:int -> value:'T -> unit.
    Fills a range of elements of the array with the given value.
  • Array.set: array:'T[] -> index:int -> value:'T -> unit.
    Sets an element of an array.
  • In addition to these, all the other BCL array functions are available as well.

I won’t give examples. See the MSDN documentation.

28. Using sequences with disposables

One important use of conversion functions like List.ofSeq is to convert a lazy enumeration (seq) to a fully evaluated collection such as list. This is particularly
important when there is a disposable resource involved such as file handle or database connection. If the sequence is not converted into a list
while the resource is available you may encounter errors accessing the elements later, after the resource has been disposed.

This will be an extended example, so let’s start with some helper functions that emulate a database and a UI:

  1. // a disposable database connection
  2. let DbConnection() = 
  3.     printfn "Opening connection"
  4.     { new System.IDisposable with
  5.         member this.Dispose() =
  6.             printfn "Disposing connection" }
  8. // read some records from the database
  9. let readNCustomersFromDb dbConnection n =
  10.     let makeCustomer i = 
  11.         sprintf "Customer %i" i
  13.     seq {
  14.         for i = 1 to n do
  15.             let customer = makeCustomer i
  16.             printfn "Loading %s from db" customer 
  17.             yield customer 
  18.         } 
  20. // show some records on the screen
  21. let showCustomersinUI customers = 
  22.     customers |> Seq.iter (printfn "Showing %s in UI")

A naive implementation will cause the sequence to be evaluated after the connection is closed:

  1. let readCustomersFromDb() =
  2.     use dbConnection = DbConnection()
  3.     let results = readNCustomersFromDb dbConnection 2
  4.     results
  6. let customers = readCustomersFromDb()
  7. customers |> showCustomersinUI

The output is below. You can see that the connection is closed and only then is the sequence evaluated.

  1. Opening connection
  2. Disposing connection
  3. Loading Customer 1 from db  // error! connection closed!
  4. Showing Customer 1 in UI
  5. Loading Customer 2 from db
  6. Showing Customer 2 in UI

A better implementation will convert the sequence to a list while the connection is open, causing the sequence to be evaluated immediately:

  1. let readCustomersFromDb() =
  2.     use dbConnection = DbConnection()
  3.     let results = readNCustomersFromDb dbConnection 2
  4.     results |> List.ofSeq
  5.     // Convert to list while connection is open
  7. let customers = readCustomersFromDb()
  8. customers |> showCustomersinUI

The result is much better. All the records are loaded before the connection is disposed:

  1. Opening connection
  2. Loading Customer 1 from db
  3. Loading Customer 2 from db
  4. Disposing connection
  5. Showing Customer 1 in UI
  6. Showing Customer 2 in UI

A third alternative is to embed the disposable in the sequence itself:

  1. let readCustomersFromDb() =
  2.     seq {
  3.         // put disposable inside the sequence
  4.         use dbConnection = DbConnection()
  5.         yield! readNCustomersFromDb dbConnection 2
  6.         } 
  8. let customers = readCustomersFromDb()
  9. customers |> showCustomersinUI

The output shows that now the UI display is also done while the connection is open:

  1. Opening connection
  2. Loading Customer 1 from db
  3. Showing Customer 1 in UI
  4. Loading Customer 2 from db
  5. Showing Customer 2 in UI
  6. Disposing connection

This may be a bad thing (longer time for the connection to stay open) or a good thing (minimal memory use), depending on the context.

29. The end of the adventure

You made it to the end — well done! Not really much of an adventure, though, was it? No dragons or anything. Nevertheless, I hope it was helpful.