序列 (F#)

更新:2010 年 5 月

“序列”是类型相同的所有元素的逻辑序列。 当您具有一个较大的有序数据集合,但并不需要使用所有元素时,序列会特别有用。 由于仅根据需要计算各个序列元素,因此在不需要使用所有元素的情况下,序列可以提供比列表更好的性能。 序列由 seq<'T> 类型表示,后者是 IEnumerable<T> 的别名。 因此,可以将实现 System.IEnumerable 的任何 .NET Framework 类型用作序列。 Seq 模块提供对涉及多个序列的操作的支持。

序列表达式

“序列表达式”是一类计算结果为序列的表达式。 序列表达式可以采用多种形式。 最简单的形式是指定一个范围。 例如,seq { 1 .. 5 } 将创建一个包含五个元素的序列(包括端点 1 和 5)。 也可以在两个双句点之间指定递增量或递减量。 例如,下面的代码将创建 10 的倍数的序列。

// 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 表达式是一个筛选器。 例如,为了生成一个只包含质数的序列,假定您具有类型 int -> bool 的函数 isprime,并按如下形式构造序列。

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# 数据类型以及任何实现 IEnumerable<T> 的 .NET Framework 数据类型一起使用。 将此函数与将列表作为参数的函数(它只能使用列表)对比。 类型 seq<'a> 是 IEnumerable<'a> 的类型缩写。 这意味着,任何实现泛型 IEnumerable<T> 的类型(包括 F# 中的数组、列表、集和映射,以及大多数 .NET Framework 集合类型)均与 seq 类型兼容,并且可以在需要序列的位置使用它。

模块函数

Microsoft.FSharp.Collections 命名空间中的 Seq 模块包含与序列一起使用的函数。 这些函数还与列表、数组、映射和集一起使用,由于所有这些类型都是可枚举的,因此可将它们视为序列。

创建序列

可以使用序列表达式(如前所述)或使用特定函数来创建序列。

可以使用 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.ofArraySeq.ofList<'T> 函数 (F#),可以从数组和列表创建序列。 不过,您也可以使用强制转换运算符将数组和列表转换成序列。 下面的代码演示了这两种方法。

// 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 使用状态的一个选项类型,这使您能够通过返回 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.existsSeq.exists2Seq.findSeq.findIndexSeq.pickSeq.tryFindSeq.tryFindIndex。 这些函数的适用于序列的各个版本在计算序列时最多计算到要搜索的元素。 有关示例,请参见列表

获取子序列

Seq.filterSeq.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

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.zipSeq.zip3 使用两个或三个序列并生成元组序列。 这些函数与可用于列表的相应函数类似。 没有用于将一个序列分成两个或更多序列的相应功能。 如果需要对序列使用此功能,请将序列转换成列表并使用 List.unzip

排序、比较和分组

列表支持的排序函数也适用于序列。 这包括 Seq.sortSeq.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.averageSeq.sumSeq.averageBySeq.sumBy 等。

Seq.foldSeq.reduceSeq.scan 都与可用于列表的相应函数类似。 序列支持列表所支持的这些函数的完全变体的子集。 有关更多信息和示例,请参见 列表 (F#)

请参见

参考

IEnumerable<T>

其他资源

F# 语言参考

F# 类型

修订记录

Date

修订记录

原因

2010 年 5 月

已改进的某些代码示例。

信息补充。