Последовательности

Последовательность — это логический ряд элементов одного типа. Последовательности особенно полезны при наличии большой упорядоченной коллекции данных, но не обязательно должны использовать все элементы. Отдельные элементы последовательности вычисляются только по мере необходимости, поэтому последовательность может обеспечить лучшую производительность, чем список в ситуациях, когда не все элементы используются. Последовательности представлены seq<'T> типом, который является псевдонимом для IEnumerable<T> . Поэтому в качестве последовательности можно использовать любой тип .NET, реализующий IEnumerable<T> интерфейс. Модуль Seq обеспечивает поддержку манипуляций с последовательностями.

Выражения последовательности

Выражение последовательности — это выражение, результатом которого является последовательность. Выражения последовательности могут принимать несколько форм. В самой простой форме указывается диапазон. Например, seq { 1 .. 5 } создает последовательность, содержащую пять элементов, включая конечные точки 1 и 5. Можно также указать шаг приращения (или уменьшение) между двумя двойными точками. Например, следующий код создает последовательность кратных 10.

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

Выражения последовательности состоят из выражений F #, создающих значения последовательности. Значения также можно формировать программно:

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

В предыдущем примере используется -> оператор, который позволяет указать выражение, значение которого станет частью последовательности. Можно использовать, только -> если каждая часть кода, следующая за ней, возвращает значение.

Кроме того, можно указать do ключевое слово с необязательным yield следующим образом:

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 }

Следующий код создает список пар координат и индексов в массиве, представляющем сетку. Обратите внимание, что for для первого выражения требуется 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)
    }

ifВыражение, используемое в последовательности, является фильтром. Например, чтобы создать последовательность только простых чисел, при условии, что имеется функция isprime типа int -> bool , создайте последовательность следующим образом.

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

Как упоминалось ранее, do требуется здесь, так как нет else ветви, которая перемещается с if . Если вы попытаетесь использовать -> , вы получите сообщение об ошибке, сообщающее, что не все ветви возвращают значение.

Ключевое слово yield!.

Иногда может потребоваться включить последовательность элементов в другую последовательность. Чтобы включить последовательность в другую последовательность, необходимо использовать yield! ключевое слово:

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

Другой способ подумать yield! заключается в том, что он выполняет сведение внутренней последовательности, а затем включает его в содержащую последовательность.

При yield! использовании в выражении все остальные одиночные значения должны использовать yield ключевое слово:

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

В предыдущем примере значение будет выдаваться x в дополнение ко всем значениям 1 для x каждого из них x .

Примеры

В первом примере используется выражение последовательности, содержащее итерацию, фильтр и оператор 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
                n
    }

for x in aSequence do
    printfn "%d" x

В следующем примере создается таблица умножения, состоящая из кортежей из трех элементов, каждый из которых состоит из двух факторов и продукта:

let multiplicationTable =
    seq {
        for i in 1..9 do
            for j in 1..9 ->
                (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, реализующему System.Collections.Generic.IEnumerable<'T> . Сравните это с функцией, которая принимает список в качестве аргумента, который может принимать только списки. Тип seq<'T> является аббревиатурой типа для IEnumerable<'T> . Это означает, что любой тип, реализующий универсальный объект System.Collections.Generic.IEnumerable<'T> , включающий массивы, списки, наборы и карты в F #, а также большинство типов коллекций .NET, совместим с seq типом и может использоваться везде, где ожидается последовательность.

Функции модуля

Модуль Seq в пространстве имен 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. офаррай и seq. офлист<>можно создавать последовательности из массивов и списков. Однако массивы и списки можно также преобразовать в последовательности с помощью оператора приведения. В следующем коде показаны оба метода.

// 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 . Такие слабо типизированные коллекции имеют тип элемента System.Object и перечисляются с помощью неуниверсального System.Collections.Generic.IEnumerable&#96;1 типа. Следующий код иллюстрирует использование Seq.cast для преобразования System.Collections.ArrayList в последовательность.

open System

let arr = ResizeArray<int>(10)

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

let seqCast = Seq.cast arr

Можно определить бесконечные последовательности с помощью функции Seq. инитинфините . Для такой последовательности необходимо предоставить функцию, которая создает каждый элемент из индекса элемента. Бесконечные последовательности возможны из-за отложенного вычисления. элементы создаются по мере необходимости путем вызова указанной функции. В следующем примере кода создается неограниченная последовательность чисел с плавающей запятой, в данном случае чередующийся ряд квадратов последовательных целых чисел.

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 использует тип параметра для состояния, что позволяет завершить последовательность, возвращая None значение. В следующем коде показаны два примера последовательностей: seq1 и fib , которые создаются unfold операцией. Первая — seq1 это просто последовательность с числами до 20. Второе, fib ,, использует unfold для расчета последовательности Фибоначчи. Поскольку каждый элемент последовательности Фибоначчи является суммой двух предыдущих чисел Фибоначчи, значение состояния является кортежем, состоящим из двух предыдущих чисел в последовательности. Начальное значение — это (1,1) первые два числа в последовательности.

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 =
    (1, 1) // Initial state
    |> Seq.unfold (fun state ->
        if (snd state > 1000) then
            None
        else
            Some(fst state + snd state, (snd state, fst state + snd state)))

printfn "\nThe sequence fib contains Fibonacci numbers."
for x in fib do printf "%d " x

Вывод выглядит следующим образом.

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.

2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597

Ниже приведен пример кода, в котором используются многие из описанных здесь функций модуля последовательности для создания и расчета значений бесконечных последовательностей. Выполнение кода может занять несколько минут.

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

Поиск и поиск элементов

Функции поддержки последовательностей доступны в списках: Seq. Exists, Seq. exists2-, Seq. Find, Seq. findIndex, Seq. Pick, Seq. tryFindи Seq. tryFindIndex. Версии этих функций, доступные для последовательностей, оценивают последовательность только до элемента, для которого выполняется поиск. Примеры см. в разделе списки.

Получение подпоследовательностей

Seq. Filter и Seq. Choose подобны соответствующим функциям, доступным для списков, за исключением того, что фильтрация и выбор не выполняются до оценки элементов последовательности.

Seq. truncate создает последовательность из другой последовательности, но ограничивает ее заданным числом элементов. Seq. take создает новую последовательность, содержащую только заданное число элементов из начала последовательности. Если в последовательности меньше элементов, чем указано для выполнения, Seq.take создает исключение System.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. парная создает новую последовательность, в которой последовательные элементы входной последовательности группируются по кортежам.

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. windowd имеет следующий 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

Выходные данные выглядят следующим образом.

Начальная последовательность:

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. компаревис . Функция сравнивает последовательные элементы в свою очередь и останавливается при обнаружении первой неравной пары. Все дополнительные элементы не участвуют в сравнении.

В следующем коде показано использование 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. каунтби принимает функцию, которая создает значение, именуемое ключом для каждого элемента. Ключ создается для каждого элемента путем вызова этой функции для каждого элемента. Seq.countBy затем возвращает последовательность, содержащую значения ключа, и количество элементов, которые создали каждое значение ключа.

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

Выходные данные выглядят следующим образом.

(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

let sequences3 =
    sequences
    |> Seq.groupBy (fun index ->
        if (index % 3 = 0) then 0
        elif (index % 3 = 1) then 1
        else 2)

sequences3 |> printSeq

Выходные данные выглядят следующим образом.

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

Можно создать последовательность, которая устраняет повторяющиеся элементы, вызывая Seq. DISTINCT. Или можно использовать Seq. дистинктби, который принимает функцию создания ключа для каждого элемента. Результирующая последовательность содержит элементы исходной последовательности, имеющие уникальные ключи. последующие элементы, которые создают дубликат ключа для более раннего элемента, отбрасываются.

В следующем примере кода показано использование 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 "Original sequence: "
printSeq inputSequence

printfn "\nSequence with distinct absolute values: "
let seqDistinctAbsoluteValue = Seq.distinctBy (fun elem -> abs elem) inputSequence
printSeq seqDistinctAbsoluteValue

Последовательностей только для чтения и кэширование

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 подобны соответствующим функциям, доступным для списков. Последовательности поддерживают подмножество всех вариантов этих функций, которые поддерживаются в списках. Дополнительные сведения и примеры см. в разделе списки.

См. также