Sequências (F#)
A seqüência é uma seqüência lógica de elementos todos de um tipo. As seqüências são particularmente úteis quando você tiver um grande, ordenados de coleta de dados, mas não necessariamente espera usar todos os elementos. Seqüência individual elementos são calculados somente como necessário, para que uma seqüência possa fornecer um desempenho melhor do que uma lista em situações em que nem todos os elementos são usados. As seqüências são representadas pelo seq<'T> tipo, que é um alias para IEnumerable. Portanto, qualquer.NET Framework que implementa System.IEnumerable pode ser usado como uma seqüência. O módulo Seq fornece suporte para manipulações que envolvem seqüências.
Expressões de seqüência
A a expressão de seqüência é uma expressão que avalia uma seqüência. Expressões de seqüência podem levar vários formulários. A forma mais simples Especifica um intervalo. Por exemplo, seq { 1 .. 5 } cria uma seqüência que contém cinco elementos, incluindo os pontos de extremidade 1 e 5. Você pode também especificar um incremento (ou decrementar) entre dois períodos duplos. Por exemplo, o código a seguir cria a seqüência de múltiplos de 10.
// Sequence that has an increment.
seq { 0 .. 10 .. 100 }
Expressões de seqüência são formadas por expressões F# que produzem valores da seqüência. Eles podem usar o yield palavra-chave para produzir valores que se tornam parte da seqüência.
Veja a seguir um exemplo.
seq { for i in 1 .. 10 do yield i * i }
Você pode usar o -> em vez do operador yield, caso em que você pode omitir a do palavra-chave, como mostrado no exemplo a seguir.
seq { for i in 1 .. 10 -> i * i }
O código a seguir gera uma lista de pares de coordenadas juntamente com um índice em uma matriz que representa a grade.
let (height, width) = (10, 10)
seq { for row in 0 .. width - 1 do
for col in 0 .. height - 1 do
yield (row, col, row*width + col)
}
Um if usado em uma seqüência de expressão é um filtro. Por exemplo, para gerar uma seqüência de apenas os números primos, supondo que você tenha uma função isprime do tipo int -> bool, construir a seqüência da seguinte maneira.
seq { for n in 1 .. 100 do if isprime n then yield n }
Quando você usa yield ou -> em uma iteração, cada iteração é esperada para gerar um único elemento da seqüência. Se cada iteração produz uma seqüência de elementos, use yield!. Nesse caso, os elementos gerados em cada iteração são concatenados para produzir a seqüência final.
Você pode combinar várias expressões juntos em uma expressão de seqüência. Os elementos gerados por cada expressão são concatenados. Por exemplo, consulte a seção "Exemplos" deste tópico.
Exemplos
O primeiro exemplo usa uma expressão de seqüência que contém uma iteração, um filtro e um rendimento para gerar uma matriz. Esse código imprime uma seqüência de números primos entre 1 e 100 para o 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 yield n }
for x in aSequence do
printfn "%d" x
O seguinte código usa yield para criar uma tabela de multiplicação consiste em tuplas de três elementos, cada uma consistindo em dois fatores e o produto.
let multiplicationTable =
seq { for i in 1..9 do
for j in 1..9 do
yield (i, j, i*j) }
O exemplo a seguir demonstra o uso de yield! para combinar seqüências individuais em uma única seqüência final. Nesse caso, as seqüências para cada subárvore em uma árvore binária são concatenadas em uma função recursiva para produzir a seqüê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 seqüências
Suportam a seqüências de muitas das mesmas funções que lista. Seqüências também oferecem suporte a operações como, por exemplo, agrupamento e a contagem usando as funções de geração de chave. Seqüências também oferecem suporte a funções mais diversificadas para extração de subseqüências.
Muitos tipos de dados, como, por exemplo, listas, matrizes, conjuntos e mapas são implicitamente seqüências porque elas são coleções enumeráveis. Uma função que leva uma seqüência como um argumento funciona com qualquer um dos comuns F# tipos de dados, em conjunto com quaisquer.Tipo de dados do NET Framework que implementa IEnumerable. Compare com uma função que tem uma lista como um argumento, o que só pode levar a listas. O tipo de seq<'a> é uma abreviação de tipo de IEnumerable<'a>. Isso significa que qualquer tipo que implementa a genérica IEnumerable, que inclui os arrays, listas, define e mapeia em F# e também a maioria.NET Framework tipos de coleção, é compatível com o seq digite e pode ser usado sempre que uma seqüência é esperada.
Funções do módulo
O módulo Seq na Microsoft.FSharp.Collections namespace contém funções para trabalhar com seqüências. Essas funções trabalham com listas, matrizes, mapas e conjuntos da mesma forma, porque todos esses tipos são enumerable e, portanto, podem ser tratados como seqüências.
Criação de seqüências
Você pode criar seqüências usando expressões de seqüência, conforme descrito anteriormente, ou usando determinadas funções.
Você pode criar uma seqüência vazia, usando Seq.empty, ou você pode criar uma seqüência de apenas um elemento especificado por meio de Seq.singleton.
let seqEmpty = Seq.empty
let seqOne = Seq.singleton 10
Você pode usar Seq.init para criar uma seqüência para o qual os elementos são criados usando uma função que você fornecer. Você também pode fornecer um tamanho para a seqüência. Essa função é exatamente como List.init, exceto que os elementos não são criados até que você itera através da seqüência. O código a seguir ilustra o uso do 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 Função Seq.ofList<'T> (F#), você pode criar seqüências de matrizes e listas. No entanto, você também pode converter matrizes e listas de seqüências utilizando um operador cast. Ambas as técnicas são mostradas no código a seguir.
// 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 seqüência de uma coleção sem rigidez de tipos, tais como aqueles definidos na System.Collections. Essas coleções sem rigidez de tipos têm o tipo de elemento Object e são enumerados usando não genérica IEnumerable tipo. O código a seguir ilustra o uso do Seq.cast para converter uma ArrayList em uma seqüência.
open System
let mutable arrayList1 = new System.Collections.ArrayList(10)
for i in 1 .. 10 do arrayList1.Add(10) |> ignore
let seqCast : seq<int> = Seq.cast arrayList1
Você pode definir seqüências infinitas, usando o Seq.initInfinite função. Para a seqüência, você deve fornecer uma função que gera a cada elemento do índice do elemento. Seqüências infinitas são possíveis devido a avaliação lenta; elementos são criados conforme necessário ao chamar a função que você especificar. O exemplo de código a seguir produz uma seqüência infinita de flutuante números de ponto, neste caso, a série alternada de recíprocos dos quadrados dos números 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 seqüência a partir de uma função de computação que leva a um estado e transforma para produzir cada elemento subseqüente na seqüência. O estado é apenas um valor que é usado para calcular cada elemento e pode alterar conforme cada elemento é calculado. O segundo argumento para Seq.unfold é o valor inicial que é usado para iniciar a seqüência. Seq.unfoldusa um tipo de opção para o estado, o que permite que você encerrar a seqüência, retornando o None valor. O código a seguir mostra dois exemplos de seqüências, seq1 e fib, que são gerados por um unfold operação. A primeira, seq1, é apenas uma seqüência simple com números até 100. O segundo, fib, usa unfold para calcular a seqüência de Fibonacci. Como cada elemento da seqüência de Fibonacci é a soma dos dois números Fibonacci anteriores, o valor de estado é uma tupla que consiste em dois números anteriores na seqüência. O valor inicial é (1,1), os dois primeiros números na seqüência.
let seq1 = Seq.unfold (fun state -> if (state > 20) then None else Some(state, state + 1)) 0
printfn "The sequence seq1 contains numbers from 0 to 20."
for x in seq1 do printf "%d " x
let fib = Seq.unfold (fun state ->
if (snd state > 1000) then None
else Some(fst state + snd state, (snd state, fst state + snd state))) (1,1)
printfn "\nThe sequence fib contains Fibonacci numbers."
for x in fib do printf "%d " x
A saída é o seguinte:
A seqüência seq1 contém números de 0 a 20.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
A fib seqüência contém números de Fibonacci.
2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597
O código a seguir é um exemplo que usa muitas das funções de módulo seqüência descritas aqui para gerar e calcular os valores de seqüências infinitas. O código pode levar alguns minutos para ser executado.
// infiniteSequences.fs
// 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 series is the series of reciprocals of whole numbers.
let harmonicSeries = generateInfiniteSequence (fun index -> float index) false
// 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 =
Seq.unfold (fun state ->
let subtotal = snd state + Seq.nth (fst state + 1) sequence
if (fst state >= length) then None
else Some(subtotal,(fst state + 1, subtotal))) (0, 0.0)
// 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)
Pesquisa e Localizando elementos
Seqüências de oferecer 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 seqüências de avaliam a seqüência somente até o elemento que está sendo procurado. Para obter exemplos, consulte lista.
Obtendo subseqüências
SEQ.Filter e Seq.choose são como as funções correspondentes que estão disponíveis para listas, exceto que a filtragem e escolhendo não ocorre até que os elementos de seqüência são avaliados.
SEQ.TRUNCATE cria uma seqüência a partir de outra seqüência, mas limita a seqüência para um número especificado de elementos. SEQ.Take cria uma nova seqüência que contém somente um número especificado de elementos desde o início de uma seqüência. Se houver menos elementos na seqüência que você especifica para tirar, Seq.take lança um InvalidOperationException. A diferença entre Seq.take e Seq.truncate é que Seq.truncate não produz um erro se o número de elementos é menos do que o número especificado.
O código a seguir mostra o comportamento da e 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 de ocorrer o erro, é o 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 booleana) e criar uma seqüência a partir de outra seqüência formada por esses elementos da seqüência original para o qual o predicado é true, mas parar antes do primeiro elemento para o qual o predicado retorna false. SEQ.Skip retorna uma seqüência que ignora um número especificado dos primeiros elementos de outra seqüência e retorna os elementos restantes. SEQ.skipWhile retorna uma seqüência que ignora os primeiros elementos de outra seqüência, desde que o predicado retornar truee, em seguida, retorna os elementos restantes, iniciando com o primeiro elemento para o qual o predicado retorna false.
O exemplo de código a seguir ilustra o comportamento do e 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 é da seguinte maneira.
1 4 9
36 49 64 81 100
16 25 36 49 64 81 100
Transformação de seqüências
SEQ.Pairwise cria uma nova seqüência na qual os elementos sucessivos da seqüê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 é parecido com Seq.pairwise, exceto que em vez de produzir uma seqüência de tuplas, ela produz uma seqüência de matrizes que contêm cópias dos elementos adjacentes (um janela) da seqüência. Você pode especificar o número de elementos adjacentes que você deseja 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 é da seguinte maneira.
Seqüê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 seqüências
SEQ.zip e Seq.zip3 levar duas ou três seqüências e produzir uma seqüência de tuplas. Essas funções são como as correspondentes funções disponíveis para lista. Não existe nenhuma funcionalidade correspondente para separar uma seqüência em dois ou mais seqüências. Se você precisar dessa funcionalidade para uma seqüência, converter a seqüência em uma lista e use List.unzip.
Classificação, comparando e agrupamento
As funções de classificação com suporte para listas também trabalham com seqüências. Isso inclui Seq.sort e Seq.sortBy. Essas funções iterar em toda a seqüência.
Comparar duas seqüências usando o Seq.compareWith função. A função compara elementos sucessivos por sua vez e pára quando encontra o primeiro par desigual. Quaisquer elementos adicionais não contribuem para a comparação.
O código a seguir mostra 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 um chave para cada elemento. Uma chave é gerada para cada elemento chamando essa função em cada elemento. Seq.countByem seguida, retorna uma seqüência que contém os valores de chave e uma contagem do número de elementos que gerou a cada valor da chave.
let mySeq1 = seq { 1.. 100 }
let printSeq seq1 = Seq.iter (printf "%A ") seq1; printfn ""
let seqResult = Seq.countBy (fun elem -> if elem % 3 = 0 then 0
elif elem % 3 = 1 then 1
else 2) mySeq1
printSeq seqResult
A saída é da seguinte maneira.
(1, 34) (2, 33) (0, 33)
A saída anterior mostra que houve 34 elementos da seqüência original que produziu a chave 1, 33 valores que produziu a chave 2 e valores de 33 que produziu a chave 0.
Você pode agrupar os elementos de uma seqüência chamando Seq.groupBy. Seq.groupByleva uma seqüência e uma função que gera uma chave de um elemento. A função é executada em cada elemento da seqüência. Seq.groupByRetorna uma seqüência de tuplas, onde o primeiro elemento de cada tupla é a chave e o segundo é uma seqüência de elementos que produzem essa chave.
O exemplo de código a seguir mostra o uso de Seq.groupBy para particionar a seqüência de números de 1 a 100 em três grupos que têm a chave distinct valores 0, 1 e 2.
let sequence = seq { 1 .. 100 }
let printSeq seq1 = Seq.iter (printf "%A ") seq1; printfn ""
let sequences3 = Seq.groupBy (fun index ->
if (index % 3 = 0) then 0
elif (index % 3 = 1) then 1
else 2) sequence
sequences3 |> printSeq
A saída é da seguinte maneira.
(1, seq [1; 4; 7; 10; ...]) (2, seq [2; 5; 8; 11; ...]) (0, seq [3; 6; 9; 12; ...])
Você pode criar uma seqüência que elimina elementos duplicados chamando Seq.distinct. Ou você pode usar Seq.distinctBy, que leva a uma função de geração de chave a ser chamado em cada elemento. A seqüência resultante contém os elementos da seqüência original que possuem chaves exclusivas; elementos posteriores que produzem uma chave duplicada a um elemento anterior serão descartados.
O exemplo de código a seguir ilustra o uso do Seq.distinct. Seq.distincté demonstrado gerando seqüências que representam números binários e, em seguida, mostrando que os elementos distintos somente 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 seqüê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 seqüência resultante não tem todos os números positivos que correspondem aos números negativos na seqüência, porque os números negativos são exibidos anteriormente na seqüência e, portanto, são selecionados em vez dos números positivos que têm o mesmo valor absoluto, ou a tecla.
let inputSequence = { -5 .. 10 }
let printSeq seq1 = Seq.iter (printf "%A ") seq1; printfn ""
printfn "Original sequence: "
printSeq inputSequence
printfn "\nSequence with distinct absolute values: "
let seqDistinctAbsoluteValue = Seq.distinctBy (fun elem -> abs elem) inputSequence
seqDistinctAbsoluteValue |> printSeq
ReadOnly e seqüências em cache
SEQ.ReadOnly cria uma cópia somente leitura de uma seqüência. Seq.readonlyé útil quando você tem uma coleção de leitura-gravação, como, por exemplo, uma matriz, e você deseja modificar a coleção original. Esta 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 o array, mas em vez de retornar uma matriz, retorna uma seqüê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 seqüência. Use Seq.cache para evitar a reavaliação de uma seqüência, ou quando você tem vários threads que usam uma seqüência, mas você deve certificar-se de que cada elemento é tratado de uma só vez. Quando você tem uma seqüência que está sendo usada por vários threads, você pode ter um segmento que enumera e calcula os valores para a seqüência original e segmentos restantes podem usar a seqüência em cache.
Executar cálculos em seqüências
Operações aritméticas simples são como os de listas, como Seq.average, Seq.sum, Seq.averageBy, Seq.sumBye assim por diante.
SEQ.Fold, Seq.reduce, e Seq.scan são como as funções correspondentes que estão disponíveis para listas. Seqüências de suportam a um subconjunto das variações dessas funções completos que lista o suporte. Para mais informações e exemplos, consulte Listas (F#).