Compartilhar via

Sequências

  • Artigo

Uma sequência é uma série lógica de elementos todos de um tipo. As sequências são particularmente úteis quando você tem uma coleção de dados grande e ordenada, mas não espera necessariamente usar todos os elementos. Elementos de sequência individuais são calculados somente conforme necessário, portanto, uma sequência pode fornecer melhor desempenho do que uma lista em situações em que nem todos os elementos são usados. As sequências são representadas pelo tipo seq<'T>, que é um alias para IEnumerable<T>. Portanto, qualquer tipo do .NET Framework que implementa a interface IEnumerable<T> pode ser usado como uma sequência. O módulo Seq fornece suporte para manipulações envolvendo sequências.

Expressões de sequência

Uma expressão de sequência é uma expressão que é avaliada como uma sequência. As expressões de sequência podem usar várias formas. O formulário mais simples especifica um intervalo. Por exemplo, seq { 1 .. 5 } cria uma sequência que contém cinco elementos, incluindo os pontos de extremidade 1 e 5. Você também pode especificar um incremento (ou decremento) entre dois períodos duplos. Por exemplo, o código a seguir cria a sequência de múltiplos de 10.

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

As expressões de sequência são compostas por expressões F# que produzem valores da sequência. Você também pode gerar valores programaticamente:

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

O exemplo anterior usa o operador ->, que permite que você especifique uma expressão cujo valor se tornará parte da sequência. Você só poderá usar -> se cada parte do código que o segue retornar um valor.

Como alternativa, você pode especificar a palavra-chave do, com um opcional yield a seguir:

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
}

O código a seguir gera uma lista de pares de coordenadas junto com um índice em uma matriz que representa a grade. Observe que a primeira expressão for requer que a especificação de do.

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

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

Uma expressão if usada em uma sequência é um filtro. Por exemplo, para gerar uma sequência de apenas números primos, supondo que você tenha uma função isprime de tipo int -> bool, construa a sequência da seguinte maneira.

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

Conforme mencionado anteriormente, do é necessário aqui porque não há nenhum branch else que vá com o if. Se você tentar usar ->, receberá um erro dizendo que nem todas as ramificações retornam um valor.

A palavra-chave yield!

Às vezes, talvez você queira incluir uma sequência de elementos em outra sequência. Para incluir uma sequência em outra sequência, você precisará usar a palavra-chave yield!:

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

Outra maneira de pensar em yield! é que ela nivela uma sequência interna e, em seguida, inclui isso na sequência que contém.

Quando yield! é usada em uma expressão, todos os outros valores individuais devem usar a palavra-chave yield:

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

O exemplo anterior produzirá o valor de x além de todos os valores de 1 para x a cada x.

Exemplos

O primeiro exemplo usa uma expressão de sequência que contém uma iteração, um filtro e um rendimento para gerar uma matriz. Esse código imprime uma sequência de números primos entre 1 e 100 no 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

O exemplo a seguir cria uma tabela de multiplicação que consiste em tuplas de três elementos, cada um consistindo em dois fatores e o produto:

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

O exemplo a seguir demonstra o uso de yield! para combinar sequências individuais em uma única sequência final. Nesse caso, as sequências para cada subárvore em uma árvore binária são concatenadas em uma função recursiva para produzir a sequência final.

// 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

Usando sequências

As sequências dão suporte a muitas das mesmas funções que as listas. As sequências também dão suporte a operações como agrupamento e contagem usando funções de geração de chave. As sequências também dão suporte a funções mais diversas para extrair subsequências.

Muitos tipos de dados, como listas, matrizes, conjuntos e mapas, são sequências implicitamente porque são coleções enumeráveis. Uma função que usa uma sequência como um argumento funciona com qualquer um dos tipos de dados comuns do F#, além de qualquer tipo de dados .NET que implementa System.Collections.Generic.IEnumerable<'T>. Contraste isso com uma função que usa uma lista como um argumento, que só pode usar listas. O tipo seq<'T> é uma abreviação de tipo para IEnumerable<'T>. Isso significa que qualquer tipo que implementa o genérico System.Collections.Generic.IEnumerable<'T>, que inclui matrizes, listas, conjuntos e mapas em F#e também a maioria dos tipos de coleção .NET, é compatível com o tipo seq e pode ser usado onde uma sequência for esperada.

Funções do módulo

O módulo Seq no namespace FSharp.Collections contém funções para trabalhar com sequências. Essas funções também funcionam com listas, matrizes, mapas e conjuntos, pois todos esses tipos são enumeráveis e, portanto, podem ser tratados como sequências.

Criando sequências

Você pode criar sequências usando expressões de sequência, conforme descrito anteriormente, ou usando determinadas funções.

Você pode criar uma sequência vazia usando Seq.empty ou pode criar uma sequência de apenas um elemento especificado usando Seq.singleton.

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

Você pode usar Seq.init para criar uma sequência para a qual os elementos são criados usando uma função que você fornece. Você também fornece um tamanho para a sequência. Essa função é exatamente como List.init, exceto que os elementos não são criados até que você itera por meio da sequência. O código a seguir ilustra o uso de Seq.init.

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

A saída é

0 10 20 30 40

Usando Seq.ofArray e Seq.ofList'T<> Function, você pode criar sequências de matrizes e listas. No entanto, você também pode converter matrizes e listas em sequências usando um operador de conversão. Ambas as técnicas são mostradas no seguinte código:

// 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

Usando Seq.cast, você pode criar uma sequência de uma coleção de tipos fracos, como as definidas em System.Collections. Essas coleções com tipo fraco têm o tipo System.Object de elemento e são enumeradas usando o tipo não genérico System.Collections.Generic.IEnumerable&#96;1. O código a seguir ilustra o uso de Seq.cast para gerar uma exceção System.Collections.ArrayList.

open System

let arr = ResizeArray<int>(10)

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

let seqCast = Seq.cast arr

Você pode definir sequências infinitas usando a função Seq.initInfinite. Para essa sequência, você fornece uma função que gera cada elemento do índice do elemento. Sequências infinitas são possíveis devido à avaliação lenta; os elementos são criados conforme necessário chamando a função especificada. O exemplo de código a seguir produz uma sequência infinita de números de ponto flutuante, nesse caso, a série alternada de recíprocos de quadrados de inteiros sucessivos.

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 gera uma sequência de uma função de computação que usa um estado e o transforma para produzir cada elemento subsequente na sequência. O estado é apenas um valor usado para calcular cada elemento e pode ser alterado conforme cada elemento é calculado. O segundo argumento é Seq.unfold o valor inicial usado para iniciar a sequência. Seq.unfold usa um tipo de opção para o estado, o que permite que você encerre a sequência retornando o valor None. O código a seguir mostra dois exemplos de sequências seq1 e fib, que são gerados por uma operação unfold. A primeira, seq1, é apenas uma sequência simples com números de até 20. A segunda, fib, usa unfold para calcular a sequência Fibonacci. Como cada elemento na sequência Fibonacci é a soma dos dois números fibonacci anteriores, o valor de estado é uma tupla que consiste nos dois números anteriores na sequência. O valor inicial é (0,1), os dois primeiros números na sequência.

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

A saída é da seguinte maneira:

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

O código a seguir é um exemplo que usa muitas das funções de módulo de sequência descritas aqui para gerar e calcular os valores de sequências infinitas. Pode levar alguns minutos para que eles sejam executados.

// 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)

Pesquisando e localizando elementos

As sequências dão suporte à funcionalidade disponível com listas: Seq.exists, Seq.exists2, Seq.find, Seq.findIndex, Seq.pick, Seq.tryFind e Seq.tryFindIndex. As versões dessas funções que estão disponíveis para sequências avaliam a sequência somente até o elemento que está sendo pesquisado. Por exemplo, consulte Listas.

Obtendo Subsequences

Seq.filter e Seq.choose são como as funções correspondentes disponíveis para listas, exceto que a filtragem e a escolha não ocorrem até que os elementos de sequência sejam avaliados.

Seq.truncate cria uma sequência de outra sequência, mas limita a sequência a um número especificado de elementos. Seq.take cria uma nova sequência que contém apenas um número especificado de elementos desde o início de uma sequência. Se houver menos elementos na sequência do que você especificar a ser tomada, Seq.take gerará System.InvalidOperationException. A diferença entre Seq.take e Seq.truncate é que Seq.truncate não produz um erro se o número de elementos for menor do que o número especificado.

O código a seguir mostra o comportamento e as diferenças entre Seq.truncate e 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

A saída, antes do erro ocorrer, é a seguinte.

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

Usando Seq.takeWhile, você pode especificar uma função de predicado (uma função booliana) e criar uma sequência de outra sequência composta por esses elementos da sequência original para a qual o predicado é true, mas parar antes do primeiro elemento para o qual o predicado retorna false. Seq.skip retorna uma sequência que ignora um número especificado dos primeiros elementos de outra sequência e retorna os elementos restantes. Seq.skipWhile retorna uma sequência que ignora os primeiros elementos de outra sequência enquanto o predicado retorna true e retorna os elementos restantes, começando com o primeiro elemento para o qual o predicado retorna false.

O exemplo de código a seguir ilustra o comportamento e as diferenças entre Seq.takeWhile, Seq.skip e 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

A saída é a seguinte.

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

Transformando sequências

Seq.pairwise cria uma nova sequência na qual elementos sucessivos da sequência de entrada são agrupados em tuplas.

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 é como Seq.pairwise, exceto que, em vez de produzir uma sequência de tuplas, ele produz uma sequência de matrizes que contêm cópias de elementos adjacentes (uma janela) da sequência. Especifique o número de elementos adjacentes desejados em cada matriz.

O exemplo de código a seguir demonstra o uso de Seq.windowed. Nesse caso, o número de elementos na janela é 3. O exemplo usa printSeq, que é definido no exemplo de código anterior.

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

A saída é a seguinte.

Sequência inicial:

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

Operações com várias sequências

Seq.zip e Seq.zip3 pegam duas ou três sequências e produzem uma sequência de tuplas. Essas funções são como as funções correspondentes disponíveis para listas. Não há funcionalidade correspondente para separar uma sequência em duas ou mais sequências. Se você precisar dessa funcionalidade para uma sequência, converta a sequência em uma lista e use List.unzip.

Classificação, comparação e agrupamento

As funções de classificação com suporte para listas também funcionam com sequências. Isso inclui Seq.sort e Seq.sortBy. Essas funções iteram por toda a sequência.

Você compara duas sequências usando a função Seq.compareWith. A função compara elementos sucessivos por sua vez e é interrompida quando encontra o primeiro par desigual. Quaisquer elementos adicionais não contribuem para a comparação.

O código a seguir demonstra o uso de 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.")

No código anterior, somente o primeiro elemento é calculado e examinado e o resultado é -1.

Seq.countBy usa uma função que gera um valor chamado uma chave para cada elemento. Uma chave é gerada para cada elemento chamando essa função em cada elemento. Seq.countBy em seguida, retorna uma sequência que contém os valores de chave e uma contagem do número de elementos que geraram cada valor da chave.

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

A saída é a seguinte.

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

A saída anterior mostra que havia 34 elementos da sequência original que produziram a chave 1, 33 valores que produziram a chave 2 e 33 valores que produziram a chave 0.

Você pode agrupar elementos de uma sequência chamando Seq.groupBy. Seq.groupBy usa uma sequência e uma função que gera uma chave de um elemento. A função é executada em cada elemento da sequência. Seq.groupBy retorna uma sequência de tuplas, em que o primeiro elemento de cada tupla é a chave e o segundo é uma sequência de elementos que produzem essa chave.

O exemplo de código a seguir mostra o uso de para a partição da Seq.groupBy sequência de números de 1 a 100 em três grupos que têm os valores de chave distintos 0, 1 e 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

A saída é a seguinte.

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

Você pode criar uma sequência que elimina elementos duplicados chamando Seq.distinct. Ou você pode usar Seq.distinctBy, que usa uma função de geração de chave para ser chamada em cada elemento. A sequência resultante contém elementos da sequência original que têm chaves exclusivas; elementos posteriores que produzem uma chave duplicada para um elemento anterior são descartados.

O exemplo de código a seguir ilustra o uso do objeto Seq.distinct. Seq.distinct é demonstrado pela geração de sequências que representam números binários e, em seguida, mostrando que os únicos elementos distintos são 0 e 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

O código a seguir demonstra Seq.distinctBy começando com uma sequência que contém números negativos e positivos e usando a função de valor absoluto como a função de geração de chave. A sequência resultante está faltando todos os números positivos que correspondem aos números negativos na sequência, pois os números negativos aparecem anteriormente na sequência e, portanto, são selecionados em vez dos números positivos que têm o mesmo valor absoluto ou chave.

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

Sequências readonly e cache

Seq.readonly cria uma cópia somente leitura de uma sequência. Seq.readonly é útil quando você tem uma coleção de leitura/gravação, como uma matriz, e não deseja modificar a coleção original. Essa função pode ser usada para preservar o encapsulamento de dados. No exemplo de código a seguir, um tipo que contém uma matriz é criado. Uma propriedade expõe a matriz, mas em vez de retornar uma matriz, ela retorna uma sequência que é criada a partir da matriz usando 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 cria uma versão armazenada de uma sequência. Use Seq.cache para evitar a reavaliação de uma sequência ou quando você tiver vários threads que usam uma sequência, mas deve garantir que cada elemento seja acionado apenas uma vez. Quando você tem uma sequência que está sendo usada por vários threads, você pode ter um thread que enumera e calcula os valores para a sequência original e os threads restantes podem usar a sequência armazenada em cache.

Executando cálculos em sequências

Operações aritméticas simples são como as de listas, como Seq.average, Seq.sum, Seq.averageBy, Seq.sumBy e assim por diante.

Seq.fold, Seq.reduce e Seq.scan são como as funções correspondentes disponíveis para listas. As sequências dão suporte a um subconjunto das variações completas dessas funções que listam o suporte. Saiba mais e obtenha exemplos em Listas.

Confira também