跳转到内容

F# 编程/序列

Add links
来自维基教科书，自由的教科书
上一步：列表 索引 下一步：集合和映射
F# : 序列

序列，通常称为序列表达式，类似于列表：两种数据结构都用于表示有序的值集合。但是，与列表不同的是，序列中的元素是在需要时（或“延迟”）计算的，而不是一次性计算。这赋予序列一些有趣的特性，例如表示无限数据结构的能力。

定义序列

[编辑 | 编辑源代码]

序列使用以下语法定义

seq { expr }

类似于列表，可以使用范围和推导来构造序列

> seq { 1 .. 10 };; (* seq ranges *)
val it : seq<int> = seq [1; 2; 3; 4; ...]

> seq { 1 .. 2 .. 10 };; (* seq ranges *)
val it : seq<int> = seq [1; 3; 5; 7; ...]

> seq {10 .. -1 .. 0};; (* descending *)
val it : seq<int> = seq [10; 9; 8; 7; ...]

> seq { for a in 1 .. 10 do yield a, a*a, a*a*a };; (* seq comprehensions *)
val it : seq<int * int * int>
= seq [(1, 1, 1); (2, 4, 8); (3, 9, 27); (4, 16, 64); ...]

序列有一个有趣的特性，这与列表不同：序列中的元素是延迟求值的，这意味着 F# 不会计算序列中的值，直到这些值真正需要。这与列表形成对比，在列表中，F# 在声明时计算列表中所有元素的值。作为演示，比较以下代码

> let intList =
    [ for a in 1 .. 10 do
        printfn "intList: %i" a
        yield a ]
        
let intSeq =
    seq { for a in 1 .. 10 do
            printfn "intSeq: %i" a
            yield a };;

val intList : int list
val intSeq : seq<int>

intList: 1
intList: 2
intList: 3
intList: 4
intList: 5
intList: 6
intList: 7
intList: 8
intList: 9
intList: 10

> Seq.item 3 intSeq;;
intSeq: 1
intSeq: 2
intSeq: 3
intSeq: 4
val it : int = 4

> Seq.item 7 intSeq;;
intSeq: 1
intSeq: 2
intSeq: 3
intSeq: 4
intSeq: 5
intSeq: 6
intSeq: 7
intSeq: 8
val it : int = 8

列表在声明时创建，但序列中的元素是在需要时创建的。

因此，序列能够表示具有任意数量元素的数据结构

> seq { 1I .. 1000000000000I };;
val it : seq<bigint> = seq [1I; 2I; 3I; 4I; ...]

上面的序列表示一个包含一万亿个元素的列表。这并不意味着序列实际上包含一万亿个元素，而是它可能包含一万亿个元素。相比之下，无法创建列表 [ 1I .. 1000000000000I ]，因为 .NET 运行时会尝试立即创建所有一万亿个元素，这肯定会消耗系统上所有可用内存，然后操作才会完成。

此外，序列可以表示无限个元素

> let allEvens = 
    let rec loop x = seq { yield x; yield! loop (x + 2) }
    loop 0;;

> for a in (Seq.take 5 allEvens) do
    printfn "%i" a;;
0
2
4
6
8
val it : unit = ()

请注意 allEvens 的定义不会终止。函数 Seq.take 返回序列中前 n 个元素。如果我们尝试遍历所有元素，fsi 会无限打印。

注意：序列由 F# 编译器实现为状态机。实际上，它们在内部管理状态，并且一次只在内存中保存最后一个生成的项。创建和遍历任意长度的序列的内存使用量是恒定的。

手动遍历序列

[编辑 | 编辑源代码]

.NET 基本类库 (BCL) 在 System.Collections.Generic 命名空间中包含两个接口

type IEnumerable<'a> =
  interface
   (* Returns an enumerator that iterates through a collection *)
    member GetEnumerator<'a> : unit -> IEnumerator<'a>
  end

type IEnumerator<'a> =
  interface
   (* Advances to the next element in the sequences. Returns true if 
      the enumerator was successfully advanced to the next element; false
      if the enumerator has passed the end of the collection. *)
    member MoveNext : unit -> bool

    (* Gets the current element in the collection. *)
    member Current : 'a

    (* Sets the enumerator to its initial position, which is 
       before the first element in the collection. *)
    member Reset : unit -> unit
  end

seq 类型定义如下

type seq<'a> = System.Collections.Generic.IEnumerable<'a>

正如你所看到的，seq 不是一个独特的 F# 类型，而只是内置 System.Collections.Generic.IEnumerable 接口的另一个名称。由于 seq/IEnumerable 是一个本地的 .NET 类型，它被设计为以更命令式的风格使用，这可以通过以下方式演示

open System
open System.Collections

let evens = seq { 0 .. 2 .. 10 } (* returns IEnumerable<int> *)

let main() =
    let evensEnumerator = evens.GetEnumerator() (* returns IEnumerator<int> *)
    while evensEnumerator.MoveNext() do
        printfn "evensEnumerator.Current: %i" evensEnumerator.Current
    
    Console.ReadKey(true) |> ignore
            
main()

此程序输出

evensEnumerator.Current: 0
evensEnumerator.Current: 2
evensEnumerator.Current: 4
evensEnumerator.Current: 6
evensEnumerator.Current: 8
evensEnumerator.Current: 10

在幕后，.NET 将每个针对集合的 for 循环转换为显式的 while 循环。换句话说，以下两段代码编译成相同的字节码

let x = [1 .. 10]
for num in x do
    printfn "%i" num

let x = [1 .. 10]
let enumerator = x.GetEnumerator()
while enumerator.MoveNext() do
    let num = enumerator.Current
    printfn "%i" num

所有可以与 for 关键字一起使用的集合都实现了 IEnumerable<'a> 接口，这个概念将在本书的后面章节中讨论。

Seq 模块

[编辑 | 编辑源代码]

类似于 List 模块，Seq 模块包含许多用于操作序列的有用函数

val append : seq<'T> -> seq<'T> -> seq<'T>

将一个序列附加到另一个序列上。
> let test = Seq.append (seq{1..3}) (seq{4..7});;
val it : seq<int> = seq [1; 2; 3; 4; ...]

val choose : ('T -> 'U option) -> seq<'T> -> seq<'U>

过滤并映射一个序列到另一个序列。
> let thisworks = seq { for nm in [ Some("James"); None; Some("John") ] |> Seq.choose id -> nm.Length }
val it : seq<int> = seq [5; 4]

val distinct : seq<'T> -> seq<'T>

返回一个过滤掉重复条目的序列。
> let dist = Seq.distinct (seq[1;2;2;6;3;2])
val it : seq<int> = seq [1; 2; 6; 3]

val exists : ('T -> bool) -> seq<'T> -> bool

确定序列中是否存在元素。
> let equalsTwo x = x=2
> let exist = Seq.exists equalsTwo (seq{3..9})
val equalsTwo : int -> bool
val it : bool = false

val filter : ('T -> bool) -> seq<'T> -> seq<'T>

构建一个新的序列，该序列由从输入序列中过滤出的元素组成。
> Seq.filter (fun x-> x%2 = 0) (seq{0..9})
val it : seq<int> = seq [0; 2; 4; 6; ...]

val fold : ('State -> 'T -> 'State) -> 'State -> seq<'T> -> 'State

从左到右反复将一个函数应用于序列中的每个元素。
> let sumSeq sequence1 = Seq.fold (fun acc elem -> acc + elem) 0 sequence1
Seq.init 10 (fun index -> index * index)
|> sumSeq
|> printfn "The sum of the elements is %d."
> 
The sum of the elements is 285.

val sumSeq : seq<int> -> int
注意：序列只能以正向方式读取，因此没有像 List 和 Array 模块中那样对应的 foldBack 函数。

val initInfinite : (int -> 'T) -> seq<'T>

生成一个包含无限个元素的序列。
> Seq.initInfinite (fun x -> x*x)
val it : seq<int> = seq [0; 1; 4; 9; ...]

val map : ('T -> 'U) -> seq<'T> -> seq<'U>

将一个类型为 'a 的序列映射到类型为 'b 的序列。
> Seq.map (fun x->x*x+2) (seq[3;5;4;3])
val it : seq<int> = seq [11; 27; 18; 11]

val item : int -> seq<'T> -> 'T

返回序列的第n个值。
> Seq.item 3 (seq {for n in 2..9 do yield n})
val it : int = 5

val take : int -> seq<'T> -> seq<'T>

返回一个新的序列，该序列由输入序列中的前n个元素组成。
> Seq.take 3 (seq{1..6})
val it : seq<int> = seq [1; 2; 3]

val takeWhile : ('T -> bool) -> seq<'T> -> seq<'T>

返回一个序列，当迭代时，它会生成底层序列的元素，直到给定谓词返回 true，并且不再返回任何元素。
> let sequenciaMenorqDez = Seq.takeWhile (fun elem -> elem < 10) (seq {for i in 0..20 do yield i+1})
val sequenciaMenorqDez : seq<int>
> sequenciaMenorqDez;;
val it : seq<int> = seq [1; 2; 3; 4; ...]

val unfold : ('State -> ('T * 'State) option) -> 'State seed -> seq<'T>

fold 的反操作：此函数只要生成器函数返回 Some，就会生成一个序列。
> let fibs = (0I, 1I) |> Seq.unfold (fun (a, b) -> Some(a, (b, a + b) ) );;

val fibs : seq<bigint>

> Seq.iter (fun x -> printf "%O " x) (Seq.take 20 fibs);;
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

unfold 中的生成器函数期望返回类型为 ('T * 'State) option。元组的第一个值被插入到序列中作为元素，元组的第二个值被作为累加器传递。fibs 函数因其简洁而巧妙，但如果你从未见过 unfold 函数，就很难理解它。以下是 unfold 的更直观演示

> let test = 1 |> Seq.unfold (fun x ->
    if x <= 5 then Some(sprintf "x: %i" x, x + 1)
    else None );;

val test : seq<string>

> Seq.iter (fun x -> printfn "%s" x) test;;
x: 1
x: 2
x: 3
x: 4
x: 5

通常，最好使用 seq 推导而不是 unfold 来生成序列。

上一步：列表 索引 下一步：集合和映射
检索自 "https://wikibooks.cn/w/index.php?title=F_Sharp_Programming/Sequences&oldid=3676062"
华夏公益教科书