Secuencias
Una secuencia es una serie lógica de elementos del mismo tipo. Las secuencias son especialmente útiles cuando tiene una colección grande y ordenada de datos, pero no necesariamente esperan usar todos los elementos. Los elementos de secuencia individuales solo se calculan según sea necesario, por lo que una secuencia puede proporcionar un mejor rendimiento que una lista en situaciones en las que no se usan todos los elementos. Las secuencias se representan mediante el tipo seq<'T>, que es un alias para IEnumerable<T>. Por lo tanto, cualquier tipo de .NET que implemente la interfaz IEnumerable<T> se puede usar como secuencia. El módulo Seq proporciona compatibilidad con manipulaciones que implican secuencias.
Expresiones de secuencia
Una expresión de secuencia es una expresión que se evalúa como una secuencia. Las expresiones de secuencia pueden tomar varias formas. El formulario más sencillo especifica un intervalo. Por ejemplo, seq { 1 .. 5 } crea una secuencia que contiene cinco elementos, incluidos los puntos de conexión 1 y 5. También puede especificar un incremento (o decremento) entre dos puntos dobles. Por ejemplo, el código siguiente crea la secuencia de múltiplo de 10.
// Sequence that has an increment.
seq { 0..10..100 }
Las expresiones de secuencia se componen de expresiones de F# que generan valores de la secuencia. También puede generar valores mediante programación:
seq { for i in 1..10 -> i * i }
En el ejemplo anterior se usa el operador ->, que permite especificar una expresión cuyo valor se convertirá en parte de la secuencia. Solo puede usar -> si cada parte del código que sigue devuelve un valor.
Como alternativa, puede especificar la palabra clave do, con un yield opcional que se indica a continuación:
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
}
El código siguiente genera una lista de pares de coordenadas junto con un índice en una matriz que representa la cuadrícula. Tenga en cuenta que la primera expresión for requiere que se especifique un 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)
}
Una expresión if usada en una secuencia es un filtro. Por ejemplo, para generar una secuencia de solo números primos, suponiendo que tenga una función isprime de tipo int -> bool, construya la secuencia como se indica a continuación.
seq {
for n in 1..100 do
if isprime n then
n
}
Como se mencionó anteriormente, do se requiere aquí porque no hay ninguna rama else que vaya con if. Si intenta usar ->, obtendrá un error que indica que no todas las ramas devuelven un valor.
La palabra clave yield!.
A veces, es posible que desee incluir una secuencia de elementos en otra secuencia. Para incluir una secuencia dentro de otra secuencia, deberá usar la palabra clave yield!:
// Repeats '1 2 3 4 5' ten times
seq {
for _ in 1..10 do
yield! seq { 1; 2; 3; 4; 5}
}
Otra manera de pensar sobre yield! es que acopla una secuencia interna y, a continuación, la incluye en la secuencia contenedora.
Cuando yield! se usa en una expresión, todos los demás valores únicos deben usar la palabra clave yield:
// Combine repeated values with their values
seq {
for x in 1..10 do
yield x
yield! seq { for i in 1..x -> i}
}
En el ejemplo anterior se generará el valor de x, además de todos los valores de 1 a x para cada x.
Ejemplos
En el primer ejemplo se usa una expresión de secuencia que contiene una iteración, un filtro y un rendimiento para generar una matriz. Este código imprime una secuencia de números primos entre 1 y 100 en la consola.
// 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
En el ejemplo siguiente se crea una tabla de multiplicación que consta de tuplas de tres elementos, cada una formada por dos factores y el producto:
let multiplicationTable =
seq {
for i in 1..9 do
for j in 1..9 -> (i, j, i * j)
}
En el ejemplo siguiente se muestra el uso de yield! para combinar secuencias individuales en una sola secuencia final. En este caso, las secuencias de cada subárbol de un árbol binario se concatenan en una función recursiva para generar la secuencia 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
Utilizar secuencias
Las secuencias admiten muchas de las mismas funciones que las listas. Las secuencias también admiten operaciones como la agrupación y el recuento mediante funciones de generación de claves. Las secuencias también admiten funciones más diversas para extraer subsecuencias.
Muchos tipos de datos, como listas, matrices, conjuntos y asignaciones, son secuencias implícitas porque son colecciones enumerables. Una función que toma una secuencia como argumento funciona con cualquiera de los tipos de datos de F# comunes, además de cualquier tipo de datos de .NET que implemente System.Collections.Generic.IEnumerable<'T>. Compare esto con una función que toma una lista como argumento, que solo puede tomar listas. El tipo seq<'T> es una abreviatura de tipo para IEnumerable<'T>. Esto significa que cualquier tipo que implemente el genérico System.Collections.Generic.IEnumerable<'T>, que incluye matrices, listas, conjuntos y asignaciones en F#, y también la mayoría de los tipos de colección de .NET, es compatible con el tipo seq y se puede usar siempre que se espere una secuencia.
Funciones del módulo
El módulo Seq del espacio de nombres FSharp.Collections contiene funciones para trabajar con secuencias. Estas funciones también funcionan con listas, matrices, mapas y conjuntos, ya que todos esos tipos son enumerables y, por tanto, se pueden tratar como secuencias.
Crear secuencias
Puede crear secuencias mediante expresiones de secuencia, como se ha descrito anteriormente, o mediante determinadas funciones.
Puede crear una secuencia vacía mediante Seq.empty o puede crear una secuencia de solo un elemento especificado mediante Seq.singleton.
let seqEmpty = Seq.empty
let seqOne = Seq.singleton 10
Puede usar Seq.init para crear una secuencia para la que se crean los elementos mediante una función que proporcione. También proporciona un tamaño para la secuencia. Esta función es igual que List.init, excepto que los elementos no se crean hasta que se recorre en iteración la secuencia. En el código siguiente, se muestra el uso de Seq.init.
let seqFirst5MultiplesOf10 = Seq.init 5 (fun n -> n * 10)
Seq.iter (fun elem -> printf "%d " elem) seqFirst5MultiplesOf10
El resultado es
0 10 20 30 40
Con Seq.ofArray y la función Seq.ofList'<T>, puede crear secuencias a partir de matrices y listas. Sin embargo, también puede convertir matrices y listas en secuencias mediante un operador de conversión. Estas dos técnicas se muestran en el siguiente 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
Mediante Seq.cast, puede crear una secuencia a partir de una colección con tipo débil, como las definidas en System.Collections. Estas colecciones con tipos débiles tienen el tipo System.Object de elemento y se enumeran mediante el tipo no genérico System.Collections.Generic.IEnumerable`1. En el código siguiente se muestra el uso de Seq.cast para convertir un System.Collections.ArrayList en una secuencia.
open System
let arr = ResizeArray<int>(10)
for i in 1 .. 10 do
arr.Add(10)
let seqCast = Seq.cast arr
Puede definir secuencias infinitas mediante la función Seq.initInfinite. Para esta secuencia, se proporciona una función que genera cada elemento a partir del índice del elemento. Las secuencias infinitas son posibles debido a la evaluación diferida; Los elementos se crean según sea necesario llamando a la función que especifique. En el ejemplo de código siguiente se genera una secuencia infinita de números de punto flotante, en este caso la serie alterna de recíprocas de cuadrados de enteros sucesivos.
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 genera una secuencia a partir de una función de cálculo que toma un estado y la transforma para generar cada elemento subsiguiente de la secuencia. El estado es simplemente un valor que se usa para calcular cada elemento y puede cambiar a medida que se calcula cada elemento. El segundo argumento para Seq.unfold es el valor inicial que se usa para iniciar la secuencia. Seq.unfold usa un tipo de opción para el estado , que permite finalizar la secuencia devolviendo el valor None. En el código siguiente se muestran dos ejemplos de secuencias, seq1 yfib, que se generan mediante una operación unfold. La primera, seq1, es simplemente una secuencia simple con números de hasta 20. El segundo, fib, usa unfold para calcular la secuencia de Fibonacci. Dado que cada elemento de la secuencia de Fibonacci es la suma de los dos números de Fibonacci anteriores, el valor de estado es una tupla que consta de los dos números anteriores de la secuencia. El valor inicial es (0,1), los dos primeros números de la secuencia.
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
La salida es como sigue:
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
El código siguiente es un ejemplo que usa muchas de las funciones del módulo de secuencia que se describen aquí para generar y calcular los valores de secuencias infinitas. El código puede tardar unos minutos en ejecutarse.
// 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)
Buscar y encontrar elementos
Las secuencias admiten la funcionalidad disponible con listas: Seq.exists, Seq.exists2, Seq.find, Seq.findIndex, Seq.pick, Seq.tryFind y Seq.tryFindIndex. Las versiones de estas funciones que están disponibles para secuencias evalúan la secuencia solo hasta el elemento que se está buscando. Para ejemplos, consulte Listas.
Obtener subsecuencias
Seq.filter y Seq.choose son como las funciones correspondientes que están disponibles para las listas, excepto que el filtrado y la elección no se producen hasta que se evalúan los elementos de secuencia.
Seq.truncate crea una secuencia a partir de otra secuencia, pero limita la secuencia a un número especificado de elementos. Seq.take crea una nueva secuencia que contiene solo un número especificado de elementos desde el principio de una secuencia. Si hay menos elementos en la secuencia que se especifican para tomar, Seq.take inicia una System.InvalidOperationException. La diferencia entre Seq.take y Seq.truncate es que Seq.truncate no produce un error si el número de elementos es menor que el número especificado.
En el código siguiente se muestra el comportamiento de y las diferencias entre Seq.truncate y 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
La salida, antes de que se produzca el error, es la siguiente.
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
Mediante Seq.takeWhile, puede especificar una función de predicado (una función booleana) y crear una secuencia a partir de otra secuencia formada por esos elementos de la secuencia original para la que el predicado es true, pero detener antes del primer elemento para el que el predicado devuelve false. Seq.skip devuelve una secuencia que omite un número especificado de los primeros elementos de otra secuencia y devuelve los elementos restantes. Seq.skipWhile devuelve una secuencia que omite los primeros elementos de otra secuencia siempre que el predicado devuelva truey, a continuación, devuelve los elementos restantes, empezando por el primer elemento para el que el predicado devuelve false.
En el ejemplo de código siguiente se muestra el comportamiento de y las diferencias entre Seq.takeWhile, Seq.skipy 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
La salida es la siguiente.
1 4 9
36 49 64 81 100
16 25 36 49 64 81 100
Transformar secuencias
Seq.pairwise crea una nueva secuencia en la que los elementos sucesivos de la secuencia de entrada se agrupan en 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 es como Seq.pairwise, excepto que, en lugar de generar una secuencia de tuplas, genera una secuencia de matrices que contienen copias de elementos adyacentes (una ventana) de la secuencia. Usted se encarga de especificar el número de elementos adyacentes que desea en cada matriz.
En el siguiente ejemplo de código se muestra el uso de Seq.windowed. En este caso, el número de elementos de la ventana es 3. En el ejemplo se usa printSeq, que se define en el ejemplo 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
La salida es la siguiente.
Secuencia 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
Operaciones con secuencias múltiples
Seq.zip y Seq.zip3 toman dos o tres secuencias y generan una secuencia de tuplas. Estas funciones son como las funciones correspondientes disponibles para las listas. No hay ninguna funcionalidad correspondiente para separar una secuencia en dos o más secuencias. Si necesita esta funcionalidad para una secuencia, convierta la secuencia en una lista y use List.unzip.
Ordenación, comparación y agrupación
Las funciones de ordenación admitidas para las listas también funcionan con secuencias. Esto incluye Seq.sort y Seq.sortBy. Estas funciones recorren en iteración toda la secuencia.
Se comparan dos secuencias mediante la función Seq.compareWith. La función compara los elementos sucesivos a su vez y se detiene cuando encuentra el primer par desigual. Los elementos adicionales no contribuyen a la comparación.
En el código siguiente se muestra el 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.")
En el código anterior, solo se calcula y examina el primer elemento y el resultado es -1.
Seq.countBy toma una función que genera un valor denominado clave para cada elemento. Se genera una clave para cada elemento mediante una llamada a esta función en cada elemento. Seq.countBy, a continuación, devuelve una secuencia que contiene los valores de clave y un recuento del número de elementos que generaron cada valor de la clave.
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
La salida es la siguiente.
(1, 34) (2, 33) (0, 33)
En la salida anterior se muestra que había 34 elementos de la secuencia original que generaron los valores clave 1, 33 que generaron la clave 2 y 33 valores que generaron la clave 0.
Puede agrupar elementos de una secuencia llamando a Seq.groupBy. Seq.groupBy toma una secuencia y una función que genera una clave a partir de un elemento. La función se ejecuta en cada elemento de la secuencia. Seq.groupBy devuelve una secuencia de tuplas, donde el primer elemento de cada tupla es la clave y el segundo es una secuencia de elementos que generan esa clave.
En el ejemplo de código siguiente se muestra el uso de Seq.groupBy para particionar la secuencia de números de 1 a 100 en tres grupos que tienen los distintos valores de clave 0, 1 y 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
La salida es la siguiente.
(1, seq [1; 4; 7; 10; ...]) (2, seq [2; 5; 8; 11; ...]) (0, seq [3; 6; 9; 12; ...])
Puede crear una secuencia que elimine los elementos duplicados llamando a Seq.distinct. También puede usar Seq.distinctBy, que toma una función que genera claves para llamar a en cada elemento. La secuencia resultante contiene elementos de la secuencia original que tienen claves únicas; Los elementos posteriores que generan una clave duplicada en un elemento anterior se descartan.
En el siguiente ejemplo de código, se muestra el uso de Seq.distinct. Seq.distinct se muestra mediante la generación de secuencias que representan números binarios y, a continuación, se muestra que los únicos elementos distintos son 0 y 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
En el código siguiente muestra Seq.distinctBy comenzando por una secuencia que contiene números negativos y positivos y utilizando la función de valor absoluto como función de generación de claves. Falta la secuencia resultante todos los números positivos que corresponden a los números negativos de la secuencia, ya que los números negativos aparecen anteriormente en la secuencia y, por tanto, se seleccionan en lugar de los números positivos que tienen el mismo valor absoluto o clave.
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
Secuencias de solo lectura y almacenadas en caché
Seq.readonly crea una copia de solo lectura de una secuencia. Seq.readonly resulta útil cuando tiene una colección de lectura y escritura, como una matriz, y no desea modificar la colección original. Esta función se puede usar para conservar la encapsulación de datos. En el ejemplo de código siguiente, se crea un tipo que contiene una matriz. Una propiedad expone la matriz, pero en lugar de devolver una matriz, devuelve una secuencia que se crea a partir de la matriz mediante 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 crea una versión almacenada de una secuencia. Use Seq.cache para evitar la reevaluación de una secuencia o cuando tenga varios subprocesos que usen una secuencia, pero debe asegurarse de que cada elemento se actúe solo una vez. Cuando tiene una secuencia que usa varios subprocesos, puede tener un subproceso que enumera y calcula los valores de la secuencia original y los subprocesos restantes pueden usar la secuencia almacenada en caché.
Realización de cálculos en secuencias
Las operaciones aritméticas simples son como las de listas, como Seq.average, Seq.sum, Seq.averageBy, Seq.sumBy, etc.
Seq.fold, Seq.reduce y Seq.scan son como las funciones correspondientes que están disponibles para las listas. Las secuencias admiten un subconjunto de las variaciones completas de estas funciones que enumera la compatibilidad. Para obtener más información y ejemplos, consulte Listas.
