F# : Sequences |

**Sequences**, commonly called **sequence expressions**, are similar to lists: both data structures are used to represent an ordered collection of values. However, unlike lists, elements in a sequence are computed *as they are needed* (or "lazily"), rather than computed all at once. This gives sequences some interesting properties, such as the capacity to represent infinite data structures.

## Defining SequencesEdit

Sequences are defined using the syntax:

seq { expr }

Similar to lists, sequences can be constructed using ranges and comprehensions:

> seq { 1 .. 10 };; (* seq ranges *) val it : seq<int> = seq [1; 2; 3; 4; ...] > seq { 1 .. 2 .. 10 };; (* seq ranges *) val it : seq<int> = seq [1; 3; 5; 7; ...] > seq {10 .. -1 .. 0};; (* descending *) val it : seq<int> = seq [10; 9; 8; 7; ...] > seq { for a in 1 .. 10 do yield a, a*a, a*a*a };; (* seq comprehensions *) val it : seq<int * int * int> = seq [(1, 1, 1); (2, 4, 8); (3, 9, 27); (4, 16, 64); ...]

Sequences have an interesting property which sets them apart from lists: elements in the sequence are *lazily evaluated*, meaning that F# does not compute values in a sequence until the values are actually needed. This is in contrast to lists, where F# computes the value of all elements in a list on declaration. As a demonstration, compare the following:

> let intList = [ for a in 1 .. 10 do printfn "intList: %i" a yield a ] let intSeq = seq { for a in 1 .. 10 do printfn "intSeq: %i" a yield a };; val intList : int list val intSeq : seq<int> intList: 1 intList: 2 intList: 3 intList: 4 intList: 5 intList: 6 intList: 7 intList: 8 intList: 9 intList: 10 > Seq.nth 3 intSeq;; intSeq: 1 intSeq: 2 intSeq: 3 intSeq: 4 val it : int = 4 > Seq.nth 7 intSeq;; intSeq: 1 intSeq: 2 intSeq: 3 intSeq: 4 intSeq: 5 intSeq: 6 intSeq: 7 intSeq: 8 val it : int = 8

The list is created on declaration, but elements in the sequence are created as they are needed.

As a result, sequences are able to represent a data structure with an arbitrary number of elements:

> seq { 1I .. 1000000000000I };; val it : seq<bigint> = seq [1I; 2I; 3I; 4I; ...]

The sequence above represents a list with one trillion elements in it. That does not mean the sequence actually contains one trillion elements, but it can *potentially* hold one trillion elements. By comparison, it would not be possible to create a list `[ 1I .. 1000000000000I ]`

since the .NET runtime would attempt to create all one trillion elements up front, which would certainly consume all of the available memory on a system before the operation completed.

Additionally, sequences can represent an infinite number of elements:

> let allEvens = let rec loop x = seq { yield x; yield! loop (x + 2) } loop 0;; > for a in (Seq.take 5 allEvens) do printfn "%i" a;; 0 2 4 6 8 val it : unit = ()

Notice the definition of `allEvens`

does not terminate. The function `Seq.take`

returns the first `n`

elements of elements of the sequence. If we attempted to loop through all of the elements, fsi would print indefinitely.

**Note:**sequences are implemented as state machines by the F# compiler. In reality, they manage state interally and hold only the last generated item in memory at a time. Memory usage is constant for creating and traversing sequences of any length.

## Iterating Through Sequences ManuallyEdit

The .NET Base Class Library (BCL) contains two interfaces in the `System.Collections.Generic`

namespace:

type IEnumerable<'a> = interface (* Returns an enumerator that iterates through a collection *) member GetEnumerator<'a> : unit -> IEnumerator<'a> end type IEnumerator<'a> = interface (* Advances to the next element in the sequences. Returns true if the enumerator was successfully advanced to the next element; false if the enumerator has passed the end of the collection. *) member MoveNext : unit -> bool (* Gets the current element in the collection. *) member Current : 'a (* Sets the enumerator to its initial position, which is before the first element in the collection. *) member Reset : unit -> unit end

The `seq`

type is defined as follows:

type seq<'a> = System.Collections.Generic.IEnumerable<'a>

As you can see, `seq`

is not a unique F# type, but rather another name for the built-in `System.Collections.Generic.IEnumerable`

interface. Since `seq`

/`IEnumerable`

is a native .NET type, it was designed to be used in a more imperative style, which can be demonstrated as follows:

open System open System.Collections let evens = seq { 0 .. 2 .. 10 } (* returns IEnumerable<int> *) let main() = let evensEnumerator = evens.GetEnumerator() (* returns IEnumerator<int> *) while evensEnumerator.MoveNext() do printfn "evensEnumerator.Current: %i" evensEnumerator.Current Console.ReadKey(true) |> ignore main()

This program outputs:

evensEnumerator.Current: 0 evensEnumerator.Current: 2 evensEnumerator.Current: 4 evensEnumerator.Current: 6 evensEnumerator.Current: 8 evensEnumerator.Current: 10

Behind the scenes, .NET converts every `for`

loop over a collection into an explicit while loop. In other words, the following two pieces of code compile down to the same bytecode:

let x = [1 .. 10] for num in x do printfn "%i" num |
let x = [1 .. 10] let enumerator = x.GetEnumerator() while enumerator.MoveNext() do let num = enumerator.Current printfn "%i" num |

All collections which can be used with the `for`

keyword implement the `IEnumerable<'a>`

interface, a concept which will be discussed later in this book.

## The `Seq`

ModuleEdit

Similar to the List modules, the `Seq`

module contains a number of useful functions for operating on sequences:

**val append : seq<'T> -> seq<'T> -> seq<'T>**

- Appends one sequence onto another sequence.

> let test = Seq.append (seq{1..3}) (seq{4..7});; val it : seq<int> = seq [1; 2; 3; 4; ...]

**val choose : ('T -> 'U option) -> seq<'T> -> seq<'U>**

- Filters and maps a sequence to another sequence.

> let thisworks = seq { for nm in [ Some("James"); None; Some("John") ] |> Seq.choose id -> nm.Length } val it : seq<int> = seq [5; 4]

**val distinct : seq<'T> -> seq<'T>**

- Returns a sequence that filters out duplicate entries.

> let dist = Seq.distinct (seq[1;2;2;6;3;2]) val it : seq<int> = seq [1; 2; 6; 3]

**val exists : ('T -> bool) -> seq<'T> -> bool**

- Determines if an element exist in a sequence.

> let igualADois x = x=2 > let existe = Seq.exists igualADois (seq{3..9}) val igualADois : int -> bool val it : bool = false

**val filter : ('T -> bool) -> seq<'T> -> seq<'T>**

- Builds a new sequence consisting of elements filtered from the input sequence.

> Seq.filter (fun x-> if x%2=0 then true else false) (seq{0..9}) val it : seq<int> = seq [0; 2; 4; 6; ...]

**val fold : ('State -> 'T -> 'State) -> 'State -> seq<'T> -> 'State**

- Repeatedly applies a function to each element in the sequence from left to right.

> let sumSeq sequence1 = Seq.fold (fun acc elem -> acc + elem) 0 sequence1 Seq.init 10 (fun index -> index * index) |> sumSeq |> printfn "The sum of the elements is %d." > The sum of the elements is 285. val sumSeq : seq<int> -> int

**Note:**sequences can only be read forward-only manner, so there is no corresponding`foldBack`

function as found in the List and Array modules.

**val initInfinite : (int -> 'T) -> seq<'T>**

- Generates a sequence consisting of an infinite number of elements.

> Seq.initInfinite (fun x -> x*x) val it : seq<int> = seq [0; 1; 4; 9; ...]

**val map : ('T -> 'U) -> seq<'T> -> seq<'U>**

- Maps a sequence of type
`'a`

to type`'b`

.

> Seq.map (fun x->x*x+2) (seq[3;5;4;3]) val it : seq<int> = seq [11; 27; 18; 11]

**val nth : int -> seq<'T> -> 'T**

- Returns the
*nth*value of a sequence.

> Seq.nth 3 (seq {for n in 2..9 do yield n}) val it : int = 5

**val take : int -> seq<'T> -> seq<'T>**

- Returns a new sequence consisting of the first
*n*elements of the input sequence.

> Seq.take 3 (seq{1..6}) val it : seq<int> = seq [1; 2; 3]

**val takeWhile : ('T -> bool) -> seq<'T> -> seq<'T>**

- Return a sequence that, when iterated, yields elements of the underlying sequence while the given predicate returns
`true`

, and returns no further elements.

> let sequenciaMenorqDez = Seq.takeWhile (fun elem -> elem < 10) (seq {for i in 0..20 do yield i+1}) val sequenciaMenorqDez : seq<int> > sequenciaMenorqDez;; val it : seq<int> = seq [1; 2; 3; 4; ...]

**val unfold : ('State -> ('T * 'State) option) -> 'State seed -> seq<'T>**

- The opposite of
`fold`

: this function generates a sequence as long as the generator function returns`Some`

.

> let fibs = (0I, 1I) |> Seq.unfold (fun (a, b) -> Some(a, (b, a + b) ) );; val fibs : seq<bigint> > Seq.iter (fun x -> printf "%O " x) (Seq.take 20 fibs);; 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

The generator function in `unfold`

expects a return type of `('T * 'State) option`

. The first value of the tuple is inserted as an element into the sequence, the second value of the tuple is passed as the accumulator. The `fibs`

function is clever for its brevity, but its hard to understand if you've never seen an unfold function. The following demonstrates `unfold`

in a more straightforward way:

> let test = 1 |> Seq.unfold (fun x -> if x <= 5 then Some(sprintf "x: %i" x, x + 1) else None );; val test : seq<string> > Seq.iter (fun x -> printfn "%s" x) test;; x: 1 x: 2 x: 3 x: 4 x: 5

Often, its preferable to generate sequences using `seq`

comprehensions rather than the `unfold`

.