Последовательности (F#)
Последовательность — это логический ряд элементов одного типа.Последовательности особенно удобны, если при наличии большой упорядоченной коллекции данных не планируется обязательное использование всех элементов.Отдельные элементы последовательности вычисляются только при необходимости, поэтому в ситуациях, в которых используется только часть элементов, последовательность может обеспечивать более высокую производительность, чем список.Последовательности представляются типом seq<'T>, являющимся псевдонимом для типа IEnumerable<T>.Поэтому в качестве последовательности может использоваться любой тип платформы .NET Framework, который реализует System.IEnumerable.Модуль Seq обеспечивает поддержку операций с последовательностями.
Выражения последовательности
Выражение последовательности представляет собой выражение, результатом которого является последовательность.Выражения последовательности могут принимать различные формы.Простейшая форма — это указание диапазона.Например, seq { 1 .. 5 } создает последовательность, содержащую пять элементов, включая конечные точки 1 и 5.Также можно указать шаг прироста (или уменьшения) между двумя двойными точками.Например, в следующем коде создается последовательность чисел, кратных десяти.
// Sequence that has an increment.
seq { 0 .. 10 .. 100 }
Выражения последовательности состоят из выражений языка F#, дающих значения последовательности.В них может использоваться ключевое слово yield, дающее значения, которые становятся частью последовательности.
Ниже приведен пример.
seq { for i in 1 .. 10 do yield i * i }
Можно использовать оператор -> вместо yield, при этом можно опустить ключевое слово do, как показано в следующем примере.
seq { for i in 1 .. 10 -> i * i }
Следующий код создает список пар координат и их индексов в массиве, который представляет сетку.
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)
}
Выражение if, используемое в последовательности, представляет собой фильтр.Например, чтобы создать последовательность простых чисел, можно создать функцию isprime, имеющую тип int -> bool, и построить последовательность следующим образом.
seq { for n in 1 .. 100 do if isprime n then yield n }
Если в итерации используется оператор yield или сочетание символов ->, ожидается, что в каждой итерация будет создаваться один элемент последовательности.Если в каждой итерации создается последовательность элементов, используйте оператор yield!.В этом случае результирующая последовательность получается путем сцепления элементов, созданных в каждой итерации.
В выражении последовательности можно использовать несколько выражений.Элементы, формируемые каждым из выражений, сцепляются между собой.Пример см. в подразделе "Примеры" данного раздела.
Примеры
В первом примере для создания массива используется выражение последовательности, содержащее итерацию, фильтр и оператор yield.Этот код выводит на консоль последовательность простых чисел в диапазоне от 1 до 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
В следующем коде с помощью оператора yield создается таблица умножения, состоящая из кортежей по три элемента, в каждом из которых содержится два множителя и произведение.
let multiplicationTable =
seq { for i in 1..9 do
for j in 1..9 do
yield (i, j, i*j) }
В следующем примере демонстрируется использование оператора yield! для объединения нескольких отдельных последовательностей в единую результирующую последовательность.В данном случае результирующая последовательность получается путем соединения последовательностей в каждом поддереве двоичного дерева с помощью рекурсивной функции.
// 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
Использование последовательностей
Последовательности поддерживают работу со многими из тех функций, с которыми работают списки.Последовательности также поддерживают такие операции, как группирование и подсчет, используя функции создания ключей.Кроме того, последовательности поддерживают более сложные функции для извлечения подпоследовательностей.
Многие типы данных, такие как списки, массивы, наборы и карты, являются неявными последовательностями, так как представляют собой перечислимые коллекции.Функция, принимающая в качестве аргумента последовательность, работает с любыми общими типами данных языка F#, помимо любых типов данных платформы .NET Framework, реализующих IEnumerable<T>.Сравните эту ситуацию с функцией, которая принимает в качестве аргумента список и может принимать только списки.Тип seq<'a> представляет собой аббревиатуру для типа IEnumerable<'a>.Это означает, что любой тип, реализующий универсальный тип IEnumerable<T>, включая массивы, списки, наборы и карты в языке F#, а также большинство типов коллекций платформы .NET Framework, совместим с типом seq и может быть использован в любом случае, в котором ожидается последовательность.
Функции модуля
Модуль Seq в пространстве имен Microsoft.FSharp.Collections содержит функции для работы с последовательностями.Эти функции также работают со списками, массивами, наборами и картами, так как эти типы являются перечислимыми и, следовательно, могут рассматриваться как последовательности.
Создание последовательностей
Последовательности можно создавать с помощью выражений последовательности, как описано выше, или с помощью некоторых функций.
Можно создать пустую последовательность, используя функцию Seq.empty, или можно создать последовательность всего из одного указанного элемента с помощью функции Seq.singleton.
let seqEmpty = Seq.empty
let seqOne = Seq.singleton 10
Функцию Seq.init можно использовать для создания последовательности, элементы которой создаются с помощью предоставленной программистом функции.Можно также указать размер последовательности.Эта функция аналогична функции List.init, за исключением того, что элементы не создаются до тех пор, пока не будет произведена итерация по последовательности.В следующем примере кода демонстрируется использование функции Seq.init.
let seqFirst5MultiplesOf10 = Seq.init 5 (fun n -> n * 10)
Seq.iter (fun elem -> printf "%d " elem) seqFirst5MultiplesOf10
Результат получается следующим:
0 10 20 30 40
С помощью функций Seq.ofArray и Функция Seq.ofList<'T> (F#) можно создавать последовательности из массивов и списков.Однако массивы и списки можно также преобразовывать в последовательности с помощью оператора cast.Оба способа иллюстрирует следующий код.
// 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
Используя функцию Seq.cast, можно создавать последовательности из слабо типизированных коллекций, таких как определенные в System.Collections.Такие слабо типизированные коллекции имеют тип элемента Object и перечисляются с использованием неуниверсального типа IEnumerable<T>.Следующий код иллюстрирует применение функции Seq.cast для преобразования типа ArrayList в последовательность.
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
С помощью функции Seq.initInfinite можно определять бесконечные последовательности.Для такой последовательности требуется предоставить функцию, создающую элемент на основе его индекса.Бесконечные последовательности возможны благодаря отложенному вычислению; элементы создаются по мере необходимости путем вызова указанной функции.В следующем примере кода создается бесконечная последовательность чисел с плавающей запятой, в данном случае знакопеременная последовательность обратных величин квадратов последовательных целых чисел.
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 создает последовательность из вычислительной функции, которая принимает состояние и преобразует его для создания каждого последующего элемента в последовательности.Состояние представляет собой просто значение, используемое для вычисления каждого элемента, и может изменяться по мере вычисления элементов.Вторым аргументом функции Seq.unfold является целое значение, используемое в качестве начала последовательности.В функции Seq.unfold в качестве состояния используется тип option, что позволяет завершить последовательность, вернув значение None.В следующем коде приведены два примера последовательностей, seq1 и fib, созданных с помощью операции unfold.Первая последовательность seq1 представляет собой простую последовательность цифр вплоть до 100.Во второй последовательности, fib, оператор unfold используется для вычисления последовательности Фибоначчи.Так как каждый элемент последовательности Фибоначчи является суммой двух предыдущих чисел Фибоначчи, значение состояния представляет собой кортеж, состоящий из двух предыдущих чисел в последовательности.Начальное значение равно (1,1) — первые два числа в последовательности.
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
Выходные данные выглядят следующим образом.
Последовательность seq1 содержит цифры от 0 до 20.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Последовательность fib содержит числа Фибоначчи.
2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597
В следующем примере кода многие из описанных в данном разделе функций модуля последовательностей используются для создания и вычисления значений бесконечных последовательностей.Выполнение кода может занять несколько минут.
// 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)
Поиск элементов
Последовательности поддерживают функции, доступные для списков: Seq.exists, Seq.exists2, Seq.find, Seq.findIndex, Seq.pick, Seq.tryFind и Seq.tryFindIndex.Варианты этих функций, доступные для последовательностей, производят вычисление последовательности только до искомого элемента.Примеры см. в разделе Списки.
Получение подпоследовательностей
Функции Seq.filter и Seq.choose аналогичны соответствующим функциям, предусмотренным для списков, за исключением того, что фильтрация и выбор производятся только после вычисления элементов последовательности.
Функция Seq.truncate создает последовательность из другой последовательности, но ограничивает ее указанным количеством элементов.Функция Seq.take создает новую последовательность, содержащую только заданное число элементов с начала последовательности.Если в последовательности меньше элементов, чем задано для получения, функция Seq.take устанавливает исключение InvalidOperationException.Различие между функциями Seq.take и Seq.truncate заключается в том, что функция Seq.truncate не дает ошибку, если количество элементов меньше указанного.
В следующем коде показано поведение функций Seq.truncate и 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
Выходные данные до возникновения ошибки выглядят следующим образом.
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
Используя функцию Seq.takeWhile, можно указать предикативную функцию (логическую функцию) и создать последовательность из другой последовательности, состоящую из тех элементов исходной последовательности, для которых предикат имеет значение true, прерывающуюся перед первым элементом, для которого предикат возвращает значение false.Функция Seq.skip возвращает последовательность, в которой пропускается указанное число начальных элементов другой последовательности и возвращаются оставшиеся элементы.Функция Seq.skipWhile возвращает последовательность, в которой первые элементы другой последовательности пропускаются, пока предикат возвращает значение true, а затем возвращаются оставшиеся элементы, начиная с первого элемента, для которого предикат возвращает значение false.
В следующем примере кода показано поведение функций Seq.takeWhile, Seq.skip и 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
Выходные данные выглядят следующим образом.
1 4 9
36 49 64 81 100
16 25 36 49 64 81 100
Преобразование последовательностей
Функция Seq.pairwise создает новую последовательность, в которой последовательные элементы входной последовательности группируются в кортежи.
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 аналогична функции Seq.pairwise, но вместо создания последовательности кортежей она создает последовательность массивов, содержащую копии соседних элементов (окно) из последовательности.Пользователь задает количество соседних элементов, которые требуется поместить в каждый массив.
В следующем примере кода показано использование функции Seq.windowed.В данном случае количество элементов в окне равно 3.В примере используется printSeq, который определен в прошлом примере кода.
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
Выходные данные выглядят следующим образом.
Initial sequence:
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
Операции с несколькими последовательностями
Функции Seq.zip и Seq.zip3 принимают две или три последовательности и создают последовательность кортежей.Эти функции аналогичны соответствующим функциям для списков.Соответствующая функция для разделения одной последовательности на две и более последовательностей отсутствует.Если требуется выполнить эту операцию для последовательности, преобразуйте ее в список и используйте функцию List.unzip.
Сортировка, сравнение и группирование
Функции сортировки, поддерживаемые для списков, работают и с последовательностями.Сюда входят функции Seq.sort и Seq.sortBy.Эти функции выполняют перебор всей последовательности.
Для сравнения двух последовательностей служит функция Seq.compareWith.Эта функция по-очереди сравнивает последовательные элементы и останавливается при обнаружении первой несовпадающей пары.Все остальные элементы не участвуют в сравнении.
В следующем коде показано использование функции 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.")
В предыдущем коде вычисляется и проверяется только первый элемент, и возвращается результат -1.
Функция Seq.countBy принимает функцию, которая для каждого элемента создает значение, называемое ключом.Ключ создается для каждого элемента путем вызова для него этой функции.Функция Seq.countBy затем возвращает последовательность, содержащую значения ключей и количество элементов, для которых получается каждое из значений ключа.
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
Выходные данные выглядят следующим образом.
(1, 34) (2, 33) (0, 33)
Приведенные выше выходные данные показывают, что 34 элемента исходной последовательности дают значение ключа 1, 33 элемента дают значение ключа 2 и 33 элемента дают значение ключа 0.
Элементы последовательности можно сгруппировать, вызвав функцию Seq.groupBy.Функция Seq.groupBy принимает последовательность и функцию, которая создает ключ для элемента.Эта функция выполняется для каждого элемента последовательности.Функция Seq.groupBy возвращает последовательность кортежей, в которой первый элемент каждого кортежа является ключом, а второй элемент — последовательностью элементов, дающих это значение ключа.
В следующем примере кода показано использование функции Seq.groupBy для разбиения последовательности чисел от 1 до 100 на три группы со значениями ключа 0, 1 и 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
Выходные данные выглядят следующим образом.
(1, seq [1; 4; 7; 10; ...]) (2, seq [2; 5; 8; 11; ...]) (0, seq [3; 6; 9; 12; ...])
Вызвав функцию Seq.distinct, можно создать последовательность, из которой удалены повторяющиеся элементы.Можно также использовать функцию Seq.distinctBy, которая принимает функцию создания ключа, вызываемую для каждого элемента.Результирующая последовательность содержит элементы исходной последовательности, имеющие уникальные ключи; последующие элементы, дающие такое же значение ключа, что и предыдущий элемент, отбрасываются.
В следующем примере кода демонстрируется использование функции Seq.distinct.В примере для функции Seq.distinct показано создание последовательностей, представляющих двоичные числа, а затем демонстрируется, что единственными различающимися элементами являются 0 и 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
Следующий код демонстрирует функцию Seq.distinctBy, начинаясь с последовательности, содержащей отрицательные и положительные числа, и используя функцию абсолютного значения для вычисления ключа.В результирующей последовательности отсутствуют все положительные числа, соответствующие отрицательным числам в последовательности, так как отрицательные числа располагаются в последовательности раньше и, следовательно, выбираются вместо положительных чисел с тем же абсолютным значением (ключом).
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
Последовательности только для чтения и кэшированные последовательности
Функция Seq.readonly создает копию последовательности, доступную только для чтения.Функция Seq.readonly удобна, если имеется коллекция только для чтения (например, массив), и вы не хотите изменять исходную коллекцию.Эта функция может использоваться для сохранения инкапсуляции данных.В следующем примере кода создается тип, содержащий массив.Свойство предоставляет массив, но вместо возврата массива оно возвращает последовательность, созданную из массива с помощью функции 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 создает сохраненную версию последовательности.Используйте функцию Seq.cache, чтобы избежать необходимости повторно оценивать последовательности или если последовательность используется несколькими потоками, но необходимо, чтобы операция применялась к каждому элементу только один раз.При наличии последовательности, используемой несколькими потоками, один поток может выполнять перечисление и вычисление значений исходной последовательности, а остальные потоки могут использовать кэшированную последовательность.
Вычисления с последовательностями
Простые арифметические операции совпадают с операциями для списков, например Seq.average, Seq.sum, Seq.averageBy, Seq.sumBy и т. д.
Функции Seq.fold, Seq.reduce и Seq.scan аналогичны соответствующим функциям для списков.Последовательности поддерживают подмножество всего разнообразия таких функций, поддерживаемых списками.Дополнительные сведения и примеры см. в разделе Списки (F#).