Sequences

A sequence is a logical series of elements all of one type. Sequences are particularly useful when you have a large, ordered collection of data but do not necessarily expect to use all of the elements. Individual sequence elements are computed only as required, so a sequence can provide better performance than a list in situations in which not all the elements are used. Sequences are represented by the seq<'T> type, which is an alias for IEnumerable<T>. Therefore, any .NET type that implements IEnumerable<T> interface can be used as a sequence. The Seq module provides support for manipulations involving sequences.

Sequence Expressions

A sequence expression is an expression that evaluates to a sequence. Sequence expressions can take a number of forms. The simplest form specifies a range. For example, seq { 1 .. 5 } creates a sequence that contains five elements, including the endpoints 1 and 5. You can also specify an increment (or decrement) between two double periods. For example, the following code creates the sequence of multiples of 10.

// Sequence that has an increment.
seq { 0..10..100 }

Sequence expressions are made up of F# expressions that produce values of the sequence. You can also generate values programmatically:

seq { for i in 1..10 -> i * i }

The previous sample uses the -> operator, which allows you to specify an expression whose value will become a part of the sequence. You can only use -> if every part of the code that follows it returns a value.

Alternatively, you can specify the do keyword, with an optional yield that follows:

seq {
    for i in 1..10 do
        yield i * i
}

// The 'yield' is implicit and doesn't need to be specified in most cases.
seq {
    for i in 1..10 do
        i * i
}

The following code generates a list of coordinate pairs along with an index into an array that represents the grid. Note that the first for expression requires a do to be specified.

let (height, width) = (10, 10)

seq {
    for row in 0 .. width - 1 do
        for col in 0 .. height - 1 -> (row, col, row * width + col)
}

An if expression used in a sequence is a filter. For example, to generate a sequence of only prime numbers, assuming that you have a function isprime of type int -> bool, construct the sequence as follows.

seq {
    for n in 1..100 do
        if isprime n then
            n
}

As mentioned previously, do is required here because there is no else branch that goes with the if. If you try to use ->, you'll get an error saying that not all branches return a value.

The yield! keyword

Sometimes, you may wish to include a sequence of elements into another sequence. To include a sequence within another sequence, you'll need to use the yield! keyword:

// Repeats '1 2 3 4 5' ten times
seq {
    for _ in 1..10 do
        yield! seq { 1; 2; 3; 4; 5}
}

Another way of thinking of yield! is that it flattens an inner sequence and then includes that in the containing sequence.

When yield! is used in an expression, all other single values must use the yield keyword:

// Combine repeated values with their values
seq {
    for x in 1..10 do
        yield x
        yield! seq { for i in 1..x -> i}
}

The previous example will produce the value of x in addition to all values from 1 to x for each x.

Examples

The first example uses a sequence expression that contains an iteration, a filter, and a yield to generate an array. This code prints a sequence of prime numbers between 1 and 100 to the console.

// Recursive isprime function.
let isprime n =
    let rec check i =
        i > n / 2 || (n % i <> 0 && check (i + 1))

    check 2

let aSequence =
    seq {
        for n in 1..100 do
            if isprime n then
                n
    }

for x in aSequence do
    printfn "%d" x

The following example creates a multiplication table that consists of tuples of three elements, each consisting of two factors and the product:

let multiplicationTable =
    seq {
        for i in 1..9 do
            for j in 1..9 -> (i, j, i * j)
    }

The following example demonstrates the use of yield! to combine individual sequences into a single final sequence. In this case, the sequences for each subtree in a binary tree are concatenated in a recursive function to produce the final sequence.

// Yield the values of a binary tree in a sequence.
type Tree<'a> =
    | Tree of 'a * Tree<'a> * Tree<'a>
    | Leaf of 'a

// inorder : Tree<'a> -> seq<'a>
let rec inorder tree =
    seq {
        match tree with
        | Tree(x, left, right) ->
            yield! inorder left
            yield x
            yield! inorder right
        | Leaf x -> yield x
    }

let mytree = Tree(6, Tree(2, Leaf(1), Leaf(3)), Leaf(9))
let seq1 = inorder mytree
printfn "%A" seq1

Using Sequences

Sequences support many of the same functions as lists. Sequences also support operations such as grouping and counting by using key-generating functions. Sequences also support more diverse functions for extracting subsequences.

Many data types, such as lists, arrays, sets, and maps are implicitly sequences because they are enumerable collections. A function that takes a sequence as an argument works with any of the common F# data types, in addition to any .NET data type that implements System.Collections.Generic.IEnumerable<'T>. Contrast this to a function that takes a list as an argument, which can only take lists. The type seq<'T> is a type abbreviation for IEnumerable<'T>. This means that any type that implements the generic System.Collections.Generic.IEnumerable<'T>, which includes arrays, lists, sets, and maps in F#, and also most .NET collection types, is compatible with the seq type and can be used wherever a sequence is expected.

Module Functions

The Seq module in the FSharp.Collections namespace contains functions for working with sequences. These functions work with lists, arrays, maps, and sets as well, because all of those types are enumerable, and therefore can be treated as sequences.

Creating Sequences

You can create sequences by using sequence expressions, as described previously, or by using certain functions.

You can create an empty sequence by using Seq.empty, or you can create a sequence of just one specified element by using Seq.singleton.

let seqEmpty = Seq.empty
let seqOne = Seq.singleton 10

You can use Seq.init to create a sequence for which the elements are created by using a function that you provide. You also provide a size for the sequence. This function is just like List.init, except that the elements are not created until you iterate through the sequence. The following code illustrates the use of Seq.init.

let seqFirst5MultiplesOf10 = Seq.init 5 (fun n -> n * 10)
Seq.iter (fun elem -> printf "%d " elem) seqFirst5MultiplesOf10

The output is

0 10 20 30 40

By using Seq.ofArray and Seq.ofList<'T> Function, you can create sequences from arrays and lists. However, you can also convert arrays and lists to sequences by using a cast operator. Both techniques are shown in the following code.

// Convert an array to a sequence by using a cast.
let seqFromArray1 = [| 1 .. 10 |] :> seq<int>

// Convert an array to a sequence by using Seq.ofArray.
let seqFromArray2 = [| 1 .. 10 |] |> Seq.ofArray

By using Seq.cast, you can create a sequence from a weakly typed collection, such as those defined in System.Collections. Such weakly typed collections have the element type System.Object and are enumerated by using the non-generic System.Collections.Generic.IEnumerable`1 type. The following code illustrates the use of Seq.cast to convert an System.Collections.ArrayList into a sequence.

open System

let arr = ResizeArray<int>(10)

for i in 1 .. 10 do
    arr.Add(10)

let seqCast = Seq.cast arr

You can define infinite sequences by using the Seq.initInfinite function. For such a sequence, you provide a function that generates each element from the index of the element. Infinite sequences are possible because of lazy evaluation; elements are created as needed by calling the function that you specify. The following code example produces an infinite sequence of floating point numbers, in this case the alternating series of reciprocals of squares of successive integers.

let seqInfinite =
    Seq.initInfinite (fun index ->
        let n = float (index + 1)
        1.0 / (n * n * (if ((index + 1) % 2 = 0) then 1.0 else -1.0)))

printfn "%A" seqInfinite

Seq.unfold generates a sequence from a computation function that takes a state and transforms it to produce each subsequent element in the sequence. The state is just a value that is used to compute each element, and can change as each element is computed. The second argument to Seq.unfold is the initial value that is used to start the sequence. Seq.unfold uses an option type for the state, which enables you to terminate the sequence by returning the None value. The following code shows two examples of sequences, seq1 and fib, that are generated by an unfold operation. The first, seq1, is just a simple sequence with numbers up to 20. The second, fib, uses unfold to compute the Fibonacci sequence. Because each element in the Fibonacci sequence is the sum of the previous two Fibonacci numbers, the state value is a tuple that consists of the previous two numbers in the sequence. The initial value is (0,1), the first two numbers in the sequence.

let seq1 =
    0 // Initial state
    |> Seq.unfold (fun state ->
        if (state > 20) then
            None
        else
            Some(state, state + 1))

printfn "The sequence seq1 contains numbers from 0 to 20."

for x in seq1 do
    printf "%d " x

let fib =
    (0, 1)
    |> Seq.unfold (fun state ->
        let cur, next = state
        if cur < 0 then  // overflow
            None
        else
            let next' = cur + next
            let state' = next, next'
            Some (cur, state') )

printfn "\nThe sequence fib contains Fibonacci numbers."
for x in fib do printf "%d " x

The output is as follows:

The sequence seq1 contains numbers from 0 to 20.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

The sequence fib contains Fibonacci numbers.

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 

The following code is an example that uses many of the sequence module functions described here to generate and compute the values of infinite sequences. The code might take a few minutes to run.

// generateInfiniteSequence generates sequences of floating point
// numbers. The sequences generated are computed from the fDenominator
// function, which has the type (int -> float) and computes the
// denominator of each term in the sequence from the index of that
// term. The isAlternating parameter is true if the sequence has
// alternating signs.
let generateInfiniteSequence fDenominator isAlternating =
    if (isAlternating) then
        Seq.initInfinite (fun index ->
            1.0 /(fDenominator index) * (if (index % 2 = 0) then -1.0 else 1.0))
    else
        Seq.initInfinite (fun index -> 1.0 /(fDenominator index))

// The harmonic alternating series is like the harmonic series
// except that it has alternating signs.
let harmonicAlternatingSeries = generateInfiniteSequence (fun index -> float index) true

// This is the series of reciprocals of the odd numbers.
let oddNumberSeries = generateInfiniteSequence (fun index -> float (2 * index - 1)) true

// This is the series of recipocals of the squares.
let squaresSeries = generateInfiniteSequence (fun index -> float (index * index)) false

// This function sums a sequence, up to the specified number of terms.
let sumSeq length sequence =
    (0, 0.0)
    |>
    Seq.unfold (fun state ->
        let subtotal = snd state + Seq.item (fst state + 1) sequence
        if (fst state >= length) then
            None
        else
            Some(subtotal, (fst state + 1, subtotal)))

// This function sums an infinite sequence up to a given value
// for the difference (epsilon) between subsequent terms,
// up to a maximum number of terms, whichever is reached first.
let infiniteSum infiniteSeq epsilon maxIteration =
    infiniteSeq
    |> sumSeq maxIteration
    |> Seq.pairwise
    |> Seq.takeWhile (fun elem -> abs (snd elem - fst elem) > epsilon)
    |> List.ofSeq
    |> List.rev
    |> List.head
    |> snd

// Compute the sums for three sequences that converge, and compare
// the sums to the expected theoretical values.
let result1 = infiniteSum harmonicAlternatingSeries 0.00001 100000
printfn "Result: %f  ln2: %f" result1 (log 2.0)

let pi = Math.PI
let result2 = infiniteSum oddNumberSeries 0.00001 10000
printfn "Result: %f pi/4: %f" result2 (pi/4.0)

// Because this is not an alternating series, a much smaller epsilon
// value and more terms are needed to obtain an accurate result.
let result3 = infiniteSum squaresSeries 0.0000001 1000000
printfn "Result: %f pi*pi/6: %f" result3 (pi*pi/6.0)

Searching and Finding Elements

Sequences support functionality available with lists: Seq.exists, Seq.exists2, Seq.find, Seq.findIndex, Seq.pick, Seq.tryFind, and Seq.tryFindIndex. The versions of these functions that are available for sequences evaluate the sequence only up to the element that is being searched for. For examples, see Lists.

Obtaining Subsequences

Seq.filter and Seq.choose are like the corresponding functions that are available for lists, except that the filtering and choosing does not occur until the sequence elements are evaluated.

Seq.truncate creates a sequence from another sequence, but limits the sequence to a specified number of elements. Seq.take creates a new sequence that contains only a specified number of elements from the start of a sequence. If there are fewer elements in the sequence than you specify to take, Seq.take throws a System.InvalidOperationException. The difference between Seq.take and Seq.truncate is that Seq.truncate does not produce an error if the number of elements is fewer than the number you specify.

The following code shows the behavior of and differences between Seq.truncate and Seq.take.

let mySeq = seq { for i in 1 .. 10 -> i*i }
let truncatedSeq = Seq.truncate 5 mySeq
let takenSeq = Seq.take 5 mySeq

let truncatedSeq2 = Seq.truncate 20 mySeq
let takenSeq2 = Seq.take 20 mySeq

let printSeq seq1 = Seq.iter (printf "%A ") seq1; printfn ""

// Up to this point, the sequences are not evaluated.
// The following code causes the sequences to be evaluated.
truncatedSeq |> printSeq
truncatedSeq2 |> printSeq
takenSeq |> printSeq
// The following line produces a run-time error (in printSeq):
takenSeq2 |> printSeq

The output, before the error occurs, is as follows.

1 4 9 16 25
1 4 9 16 25 36 49 64 81 100
1 4 9 16 25
1 4 9 16 25 36 49 64 81 100

By using Seq.takeWhile, you can specify a predicate function (a Boolean function) and create a sequence from another sequence made up of those elements of the original sequence for which the predicate is true, but stop before the first element for which the predicate returns false. Seq.skip returns a sequence that skips a specified number of the first elements of another sequence and returns the remaining elements. Seq.skipWhile returns a sequence that skips the first elements of another sequence as long as the predicate returns true, and then returns the remaining elements, starting with the first element for which the predicate returns false.

The following code example illustrates the behavior of and differences between Seq.takeWhile, Seq.skip, and Seq.skipWhile.

// takeWhile
let mySeqLessThan10 = Seq.takeWhile (fun elem -> elem < 10) mySeq
mySeqLessThan10 |> printSeq

// skip
let mySeqSkipFirst5 = Seq.skip 5 mySeq
mySeqSkipFirst5 |> printSeq

// skipWhile
let mySeqSkipWhileLessThan10 = Seq.skipWhile (fun elem -> elem < 10) mySeq
mySeqSkipWhileLessThan10 |> printSeq

The output is as follows.

1 4 9
36 49 64 81 100
16 25 36 49 64 81 100

Transforming Sequences

Seq.pairwise creates a new sequence in which successive elements of the input sequence are grouped into tuples.

let printSeq seq1 = Seq.iter (printf "%A ") seq1; printfn ""
let seqPairwise = Seq.pairwise (seq { for i in 1 .. 10 -> i*i })
printSeq seqPairwise

printfn ""
let seqDelta = Seq.map (fun elem -> snd elem - fst elem) seqPairwise
printSeq seqDelta

Seq.windowed is like Seq.pairwise, except that instead of producing a sequence of tuples, it produces a sequence of arrays that contain copies of adjacent elements (a window) from the sequence. You specify the number of adjacent elements you want in each array.

The following code example demonstrates the use of Seq.windowed. In this case the number of elements in the window is 3. The example uses printSeq, which is defined in the previous code example.

let seqNumbers = [ 1.0; 1.5; 2.0; 1.5; 1.0; 1.5 ] :> seq<float>
let seqWindows = Seq.windowed 3 seqNumbers
let seqMovingAverage = Seq.map Array.average seqWindows
printfn "Initial sequence: "
printSeq seqNumbers
printfn "\nWindows of length 3: "
printSeq seqWindows
printfn "\nMoving average: "
printSeq seqMovingAverage

The output is as follows.

Initial sequence:

1.0 1.5 2.0 1.5 1.0 1.5

Windows of length 3:
[|1.0; 1.5; 2.0|] [|1.5; 2.0; 1.5|] [|2.0; 1.5; 1.0|] [|1.5; 1.0; 1.5|]

Moving average:
1.5 1.666666667 1.5 1.333333333

Operations with Multiple Sequences

Seq.zip and Seq.zip3 take two or three sequences and produce a sequence of tuples. These functions are like the corresponding functions available for lists. There is no corresponding functionality to separate one sequence into two or more sequences. If you need this functionality for a sequence, convert the sequence to a list and use List.unzip.

Sorting, Comparing, and Grouping

The sorting functions supported for lists also work with sequences. This includes Seq.sort and Seq.sortBy. These functions iterate through the whole sequence.

You compare two sequences by using the Seq.compareWith function. The function compares successive elements in turn, and stops when it encounters the first unequal pair. Any additional elements do not contribute to the comparison.

The following code shows the use of Seq.compareWith.

let sequence1 = seq { 1 .. 10 }
let sequence2 = seq { 10 .. -1 .. 1 }

// Compare two sequences element by element.
let compareSequences =
    Seq.compareWith (fun elem1 elem2 ->
        if elem1 > elem2 then 1
        elif elem1 < elem2 then -1
        else 0)

let compareResult1 = compareSequences sequence1 sequence2
match compareResult1 with
| 1 -> printfn "Sequence1 is greater than sequence2."
| -1 -> printfn "Sequence1 is less than sequence2."
| 0 -> printfn "Sequence1 is equal to sequence2."
| _ -> failwith("Invalid comparison result.")

In the previous code, only the first element is computed and examined, and the result is -1.

Seq.countBy takes a function that generates a value called a key for each element. A key is generated for each element by calling this function on each element. Seq.countBy then returns a sequence that contains the key values, and a count of the number of elements that generated each value of the key.

let mySeq1 = seq { 1.. 100 }

let printSeq seq1 = Seq.iter (printf "%A ") seq1

let seqResult =
    mySeq1
    |> Seq.countBy (fun elem ->
        if elem % 3 = 0 then 0
        elif elem % 3 = 1 then 1
        else 2)

printSeq seqResult

The output is as follows.

(1, 34) (2, 33) (0, 33)

The previous output shows that there were 34 elements of the original sequence that produced the key 1, 33 values that produced the key 2, and 33 values that produced the key 0.

You can group elements of a sequence by calling Seq.groupBy. Seq.groupBy takes a sequence and a function that generates a key from an element. The function is executed on each element of the sequence. Seq.groupBy returns a sequence of tuples, where the first element of each tuple is the key and the second is a sequence of elements that produce that key.

The following code example shows the use of Seq.groupBy to partition the sequence of numbers from 1 to 100 into three groups that have the distinct key values 0, 1, and 2.

let sequence = seq { 1 .. 100 }

let printSeq seq1 = Seq.iter (printf "%A ") seq1

let sequences3 =
    sequences
    |> Seq.groupBy (fun index ->
        if (index % 3 = 0) then 0
        elif (index % 3 = 1) then 1
        else 2)

sequences3 |> printSeq

The output is as follows.

(1, seq [1; 4; 7; 10; ...]) (2, seq [2; 5; 8; 11; ...]) (0, seq [3; 6; 9; 12; ...])

You can create a sequence that eliminates duplicate elements by calling Seq.distinct. Or you can use Seq.distinctBy, which takes a key-generating function to be called on each element. The resulting sequence contains elements of the original sequence that have unique keys; later elements that produce a duplicate key to an earlier element are discarded.

The following code example illustrates the use of Seq.distinct. Seq.distinct is demonstrated by generating sequences that represent binary numbers, and then showing that the only distinct elements are 0 and 1.

let binary n =
    let rec generateBinary n =
        if (n / 2 = 0) then [n]
        else (n % 2) :: generateBinary (n / 2)

    generateBinary n
    |> List.rev
    |> Seq.ofList

printfn "%A" (binary 1024)

let resultSequence = Seq.distinct (binary 1024)
printfn "%A" resultSequence

The following code demonstrates Seq.distinctBy by starting with a sequence that contains negative and positive numbers and using the absolute value function as the key-generating function. The resulting sequence is missing all the positive numbers that correspond to the negative numbers in the sequence, because the negative numbers appear earlier in the sequence and therefore are selected instead of the positive numbers that have the same absolute value, or key.

let inputSequence = { -5 .. 10 }
let printSeq seq1 = Seq.iter (printf "%A ") seq1

printfn "Original sequence: "
printSeq inputSequence

printfn "\nSequence with distinct absolute values: "
let seqDistinctAbsoluteValue = Seq.distinctBy (fun elem -> abs elem) inputSequence
printSeq seqDistinctAbsoluteValue

Readonly and Cached Sequences

Seq.readonly creates a read-only copy of a sequence. Seq.readonly is useful when you have a read-write collection, such as an array, and you do not want to modify the original collection. This function can be used to preserve data encapsulation. In the following code example, a type that contains an array is created. A property exposes the array, but instead of returning an array, it returns a sequence that is created from the array by using Seq.readonly.

type ArrayContainer(start, finish) =
    let internalArray = [| start .. finish |]
    member this.RangeSeq = Seq.readonly internalArray
    member this.RangeArray = internalArray

let newArray = new ArrayContainer(1, 10)
let rangeSeq = newArray.RangeSeq
let rangeArray = newArray.RangeArray

// These lines produce an error:
//let myArray = rangeSeq :> int array
//myArray[0] <- 0

// The following line does not produce an error.
// It does not preserve encapsulation.
rangeArray[0] <- 0

Seq.cache creates a stored version of a sequence. Use Seq.cache to avoid reevaluation of a sequence, or when you have multiple threads that use a sequence, but you must make sure that each element is acted upon only one time. When you have a sequence that is being used by multiple threads, you can have one thread that enumerates and computes the values for the original sequence, and remaining threads can use the cached sequence.

Performing Computations on Sequences

Simple arithmetic operations are like those of lists, such as Seq.average, Seq.sum, Seq.averageBy, Seq.sumBy, and so on.

Seq.fold, Seq.reduce, and Seq.scan are like the corresponding functions that are available for lists. Sequences support a subset of the full variations of these functions that lists support. For more information and examples, see Lists.

See also

• F# Language Reference
• F# Types