Secuencias (F#)
Una secuencia es una serie lógica de elementos del mismo tipo. Las secuencias son sobre todo útiles en el caso de colecciones grandes y ordenadas de datos cuyos elementos no se van a utilizar necesariamente todos. Cada elemento de secuencia se procesa únicamente cuando es necesario, por lo que su rendimiento es mejor que el de una lista en los casos donde no se usan todos los elementos. Las secuencias vienen representadas por el tipo seq<'T>, que es un alias de IEnumerable. Por consiguiente, cualquier tipo de .NET Framework que implemente System.IEnumerable puede utilizarse como una secuencia. El módulo Seq proporciona compatibilidad con las manipulaciones en las que se utilizan 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 tener varios formatos. En su formato más sencillo, especifican un rango. Por ejemplo, seq { 1 .. 5 } crea una secuencia que contiene cinco elementos, incluidos los extremos 1 y 5. Además, se puede especificar un incremento (o decremento) entre dos puntos seguidos. Por ejemplo, el siguiente código crea la secuencia de múltiplos de 10.
// Sequence that has an increment.
seq { 0 .. 10 .. 100 }
Las expresiones de secuencia se componen de expresiones de F# que generan los valores de la secuencia. Pueden utilizar la palabra clave yield para generar valores que pasan a formar parte de la secuencia.
A continuación, se muestra un ejemplo.
seq { for i in 1 .. 10 do yield i * i }
Se puede usar el operador -> en lugar de yield, en cuyo caso se puede omitir la palabra clave do, tal y como se muestra en el siguiente ejemplo.
seq { for i in 1 .. 10 -> 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.
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)
}
Una expresión if utilizada en una secuencia es un filtro. Por ejemplo, para generar una secuencia de solo números primos y suponiendo que tiene una función isprime de tipo int -> bool, proceda de la siguiente manera.
seq { for n in 1 .. 100 do if isprime n then yield n }
Cuando se utiliza yield o -> en una iteración, se espera que cada iteración genere un solo elemento de la secuencia. Si cada iteración genera una secuencia de elementos, se utiliza yield!. En ese caso, los elementos generados en cada iteración se concatenan para generar la secuencia definitiva.
Se pueden combinar varias expresiones en una expresión de secuencia. Se concatenan los elementos generados por cada expresión. Para obtener un ejemplo, vea la sección "Ejemplos" de este tema.
Ejemplos
En el primer ejemplo, se usa una expresión de secuencia que contiene una iteración, un filtro y la palabra clave yield para generar una matriz. Este código imprime en la consola una secuencia de números primos comprendidos entre 1 y 100.
// 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
En el código siguiente, se utiliza yield para crear una tabla de multiplicar que consta de tuplas de tres elementos, cada una de ellas consistente en dos factores y el producto.
let multiplicationTable =
seq { for i in 1..9 do
for j in 1..9 do
yield (i, j, i*j) }
En el ejemplo siguiente se muestra el uso de yield! para combinar secuencias individuales en una sola secuencia definitiva. En este caso, se concatenan las secuencias de cada subárbol de un árbol binario en una función recursiva para generar la secuencia definitiva.
// 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 un gran número de las funciones admitidas por las listas. También admiten operaciones como la agrupación y el recuento mediante funciones de generación de claves. Además, admiten funciones más diversas para extraer subsecuencias.
Muchos tipos de datos, como listas, matrices, conjuntos y asignaciones son implícitamente secuencias porque son colecciones enumerables. Las funciones que toman una secuencia como argumento pueden usarse con cualquiera de los tipos de datos comunes de F#, además de los tipos de datos de .NET Framework que implementan IEnumerable. Esto contrasta con las funciones que toman una lista como argumento, ya que solo pueden tomar listas. El tipo seq<'a> es una abreviatura del tipo IEnumerable<'a>. Esto significa que cualquier tipo que implemente la colección genérica IEnumerable, que incluye matrices, listas, conjuntos y asignaciones en F#, y también la mayoría de los tipos de colección de .NET Framework, es compatible con el tipo seq y se puede utilizar cada vez que se espera una secuencia.
Funciones de módulo
El módulo Seq del espacio de nombres Microsoft.FSharp.Collections contiene funciones que permiten trabajar con secuencias. Estas funciones se pueden usar con listas, matrices, asignaciones y conjuntos, porque todos esos tipos son enumerables y, por consiguiente, se pueden tratar como secuencias.
Crear secuencias
Se pueden crear secuencias mediante expresiones de secuencia, tal y como se ha descrito anteriormente, o mediante determinadas funciones.
Para crear una secuencia vacía, se utiliza Seq.empty; para crear una secuencia de un solo elemento especificado, se usa Seq.singleton.
let seqEmpty = Seq.empty
let seqOne = Seq.singleton 10
Se puede utilizar Seq.init para generar una secuencia cuyos elementos se crean mediante una función que se proporciona. También se proporciona el tamaño de la secuencia. Esta función es similar a List.init, excepto en que los elementos no se crean hasta que se realice una iteración por 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
Mediante Seq.ofArray y Seq.ofList<'T> (Función de F#), se pueden crear secuencias a partir de matrices y listas. Sin embargo, también se puede utilizar un operador de conversión para convertir matrices y listas en secuencias. Ambas técnicas se muestran en el código siguiente.
// 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, se puede crear una secuencia a partir de una colección débilmente tipada, como las definidas en el espacio de nombres System.Collections. Las colecciones débilmente tipadas tienen elementos de tipo Object y se enumeran mediante el tipo IEnumerable no genérico. En el siguiente código, se muestra el uso de Seq.cast para convertir una colección ArrayList en una secuencia.
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
Para definir secuencias infinitas, se utiliza la función Seq.initInfinite. Para este tipo de secuencia, se proporciona una función que genera cada elemento a partir de su índice. Las secuencias infinitas son posibles gracias a la evaluación diferida; los elementos se crean según sea necesario invocando la función especificada. En el siguiente ejemplo de código, se genera una secuencia infinita de números de punto flotante; en este caso, una serie alterna de cuadrados inversos 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 crea una secuencia a partir de una función de cálculo que toma un estado y lo transforma para generar cada elemento subsiguiente de la secuencia. El estado es simplemente un valor que se utiliza para calcular cada elemento y puede cambiar cada vez que se calcula un elemento. El segundo argumento de Seq.unfold es el valor inicial que se utiliza para iniciar la secuencia. Seq.unfold utiliza un tipo de opción para el estado, lo que permite terminar la secuencia devolviendo el valor None. En el siguiente código, se muestran dos ejemplos de secuencias, seq1 y fib, que se generan mediante una operación unfold. La primera, seq1, es una secuencia simple de números hasta 100. La segunda, fib, utiliza 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 (1,1), los dos primeros números de la secuencia.
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
La salida es la siguiente:
La secuencia seq1 contiene los números del 0 al 20.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
La secuencia fib contiene números de Fibonacci.
2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597
En el siguiente código de ejemplo, se utilizan muchas de las funciones de módulo que se han descrito anteriormente para generar y calcular los valores de las secuencias infinitas. Puede que el código tarde unos minutos en ejecutarse.
// 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)
Buscar y encontrar elementos
Las secuencias admiten la funcionalidad que está disponible con las 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 las secuencias solo evalúan la secuencia hasta el elemento que se busca. Para obtener ejemplos, vea Listas.
Obtener subsecuencias
Seq.filter y Seq.choose son similares a las funciones correspondientes que están disponibles para las listas, excepto en que el filtrado y la elección no se producen hasta que se evalúan los elementos de la secuencia.
Seq.truncate crea una secuencia a partir de otra, pero la limita a un número especificado de elementos. Seq.take crea una nueva secuencia que contiene solo el número especificado de elementos contados desde el principio de una secuencia. Si la secuencia contiene menos elementos del número especificado, Seq.take produce una excepción InvalidOperationException. La diferencia entre Seq.take y Seq.truncate reside en que Seq.truncate no genera un error si el número de elementos es menor que el número especificado.
En el siguiente código, se muestran el comportamiento 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, se puede especificar una función de predicado (función booleana) y crear una secuencia a partir de otra secuencia que consta de los elementos de la secuencia original para los cuales el valor del predicado es true, pero finaliza antes del primer elemento para el cual el predicado devuelve false. Seq.skip devuelve una secuencia que omite un número especificado de los primeros elementos de otra secuencia y, a continuación, devuelve los elementos restantes. Seq.skipWhile devuelve una secuencia que omite los primeros elementos de otra secuencia para los cuales el predicado devuelve true y, a continuación, devuelve los elementos restantes, a partir del primer elemento para el cual el predicado devuelve false.
En el siguiente ejemplo de código, se muestran el comportamiento y las diferencias entre Seq.takeWhile, Seq.skip y 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 donde los elementos sucesivos de la secuencia de entrada están agrupados 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 similar a Seq.pairwise, excepto en que no genera una secuencia de tuplas sino una secuencia de matrices que contienen copias de los elementos adyacentes (ventana) de la secuencia. El usuario especifica el número de elementos adyacentes que desea incluir en cada matriz.
En el ejemplo de código siguiente, se muestra el uso de Seq.windowed. En este caso, hay 3 elementos en la ventana. 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 varias secuencias
Seq.zip y Seq.zip3 toman dos o tres secuencias y generan una secuencia de tuplas. Estas funciones son similares a las funciones correspondientes que están 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 utilice List.unzip.
Ordenar, comparar y agrupar
Las funciones de ordenación admitidas para las listas también se pueden usar con las secuencias. Entre estas funciones se incluyen Seq.sort y Seq.sortBy. Estas funciones recorren en iteración toda la secuencia.
Para comparar dos secuencias, se utiliza la función Seq.compareWith. La función compara los elementos sucesivos y se detiene cuando detecta el primer par desigual. Los elementos restantes 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 procesa y se examina el primer elemento; 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 invocando esta función en cada uno de los elementos. A continuación, Seq.countBy devuelve una secuencia que contiene los valores de clave y el número de elementos que generaron cada valor de clave.
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
La salida es la siguiente.
(1, 34) (2, 33) (0, 33)
En la salida anterior, se muestra que 34 elementos de la secuencia original generaron la clave 1, 33 valores generaron la clave 2, y 33 valores generaron la clave 0.
Para agrupar los elementos de una secuencia, se invoca 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 los elementos que generan dicha clave.
En el siguiente ejemplo de código, se muestra el uso de Seq.groupBy para dividir la secuencia de números del 1 al 100 en tres grupos con los valores de clave 0, 1 y 2, respectivamente.
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
La salida es la siguiente.
(1, seq [1; 4; 7; 10; ...]) (2, seq [2; 5; 8; 11; ...]) (0, seq [3; 6; 9; 12; ...])
Para crear una secuencia que elimina los elementos duplicados, se invoca Seq.distinct. También se puede utilizar Seq.distinctBy, que toma una función de generación de claves que se va a invocar en cada elemento. La secuencia resultante contiene los elementos de la secuencia original que tienen claves únicas; se descartan los elementos posteriores que generan una clave duplicada en un elemento anterior.
En el siguiente ejemplo de código, se muestra el uso de Seq.distinct. Para ello, se generan secuencias que representan números binarios y, a continuación, se muestra que los únicos elementos distintos son el 0 y el 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 siguiente código, se muestra el uso de Seq.distinctBy. Para ello, se usa una secuencia de números negativos y positivos y se utiliza la función de valor absoluto como función de generación de claves. La secuencia resultante no contiene ninguno de los números positivos correspondientes a los números negativos de la secuencia porque los números negativos aparecen antes en la secuencia y, por consiguiente, quedan seleccionados 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 ""
printfn "Original sequence: "
printSeq inputSequence
printfn "\nSequence with distinct absolute values: "
let seqDistinctAbsoluteValue = Seq.distinctBy (fun elem -> abs elem) inputSequence
seqDistinctAbsoluteValue |> printSeq
Secuencias de solo lectura y almacenadas en caché
Seq.readonly crea una copia de solo lectura de una secuencia. La función Seq.readonly resulta útil en el caso de una colección de lectura y escritura, como una matriz, y no se desea modificar la colección original. Esta función se puede utilizar para conservar la encapsulación de datos. En el siguiente ejemplo de código, se crea un tipo que contiene una matriz. Una propiedad expone la matriz pero, en lugar de devolver una matriz, devuelve una secuencia que creada a partir de la matriz mediante la función 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. Utilice Seq.cache para evitar una nueva evaluación de una secuencia, o cuando hay varios subprocesos que utilizan una secuencia; sin embargo, es necesario comprobar que la función se aplique solo una vez a cada elemento. En el caso de una secuencia utilizada por varios subprocesos, uno de ellos puede enumerar y procesar los valores de la secuencia original mientras que los subprocesos restantes pueden usar la secuencia almacenada en caché.
Realizar cálculos con secuencias
Se pueden realizar las operaciones aritméticas simples que están disponibles para las listas, como Seq.average, Seq.sum, Seq.averageBy, Seq.sumBy, etc.
Seq.fold, Seq.reduce y Seq.scan son similares a las funciones correspondientes que están disponibles para las listas. Las secuencias admiten un subconjunto de todas las variantes de las funciones admitidas por las listas. Para obtener más información y ejemplos, vea Listas (F#).