Бөлісу құралы:

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

  • Мақала

Последовательность — это логический ряд элементов всех одного типа. Последовательности особенно полезны, если у вас есть большая упорядоченная коллекция данных, но не обязательно предполагается использовать все элементы. Отдельные элементы последовательности вычисляются только по мере необходимости, поэтому последовательность может обеспечить лучшую производительность, чем список в ситуациях, в которых не все элементы используются. Последовательности представлены типом 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 в дополнение ко всем значениям от 1x каждого из них x.

Примеры

В первом примере используется выражение последовательности, содержащее итерацию, фильтр и выход для создания массива. Этот код выводит последовательность простых чисел от 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.ofArray и Seq.ofList'T<> можно создавать последовательности из массивов и списков. Однако можно также преобразовать массивы и списки в последовательности с помощью оператора приведения. Оба метода показаны в следующем коде.

// 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.castSystem.Collections.ArrayList преобразования в последовательность.

open System

let arr = ResizeArray<int>(10)

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

let seqCast = Seq.cast arr

Бесконечные последовательности можно определить с помощью функции 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 использует тип параметра для состояния, который позволяет завершить последовательность, возвращая None значение. В следующем коде показаны два примера последовательностей и seq1fib, созданных операцией unfold . Во-первых, seq1это просто простая последовательность с числами до 20. Во-вторых, fibиспользуется unfold для вычисления последовательности Fibonacci. Так как каждый элемент в последовательности Fibonacci является суммой предыдущих двух чисел Fibonacci, значение состояния — это кортеж, состоящий из предыдущих двух чисел в последовательности. Начальное значение — первые (0,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 =
    (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

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

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

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

// 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.takeTime, можно указать функцию предиката (логическую функцию) и создать последовательность из другой последовательности, состоящей из этих элементов исходной последовательности, для которой является trueпредикат, но остановиться перед первым элементом, для которого возвращается falseпредикат. Seq.skip возвращает последовательность, которая пропускает указанное число первых элементов другой последовательности и возвращает оставшиеся элементы. Seq.skipTime возвращает последовательность, которая пропускает первые элементы другой последовательности до тех пор, пока предикат возвращает 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

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

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

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

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

См. также