# F Sharp Programming/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 Sequences

Sequences are defined using the syntax:
Similar to lists, sequences can be constructed using ranges and comprehensions:
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:
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:
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:
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 internally 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 Manually

The .NET Base Class Library (BCL) contains two interfaces in the System.Collections.Generic namespace:
The seq type is defined as follows:
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:
This program outputs:
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 Module

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.
val choose : ('T -> 'U option) -> seq<'T> -> seq<'U>
    Filters and maps a sequence to another sequence.
val distinct : seq<'T> -> seq<'T>
    Returns a sequence that filters out duplicate entries.
val exists : ('T -> bool) -> seq<'T> -> bool
    Determines if an element exists in a sequence.
val filter : ('T -> bool) -> seq<'T> -> seq<'T>
    Builds a new sequence consisting of elements filtered from the input sequence.
val fold : ('State -> 'T -> 'State) -> 'State -> seq<'T> -> 'State
    Repeatedly applies a function to each element in the sequence from left to right.
    Note: sequences can only be read in a 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.
val map : ('T -> 'U) -> seq<'T> -> seq<'U>
    Maps a sequence of type 'a to type 'b.
val item : int -> seq<'T> -> 'T
    Returns the nth value of a sequence.
val take : int -> seq<'T> -> seq<'T>
    Returns a new sequence consisting of the first n elements of the input sequence.
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.
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.
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 it's hard to understand if you've never seen an unfold function. The following demonstrates unfold in a more straightforward way:
Often, it's preferable to generate sequences using seq comprehensions rather than the unfold.