跳轉到內容

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://wikibook.tw/w/index.php?title=F_Sharp_Programming/Sequences&oldid=3676062"
華夏公益教科書