跳轉到內容

F# 程式設計/列表

Add links
來自華夏公益教科書，開放的書籍，開放的世界
< F# 程式設計
最新稽核版本是 19 June 2023。目前有 1 個待審更改。
前一頁：元組和記錄 索引 下一頁：序列
F#：列表

列表是一個有序的關聯值的集合，它大致相當於許多其他語言中使用的連結串列資料結構。F# 提供了一個模組 Microsoft.FSharp.Collections.List，用於對列表進行常見操作；此模組由 F# 自動匯入，因此 List 模組已可從每個 F# 應用程式訪問。

建立列表

[編輯 | 編輯原始碼]

使用列表字面量

[編輯 | 編輯原始碼]

在 F# 中建立列表有很多方法，最直接的方法是用分號分隔的值序列。以下是在 fsi 中的數字列表

> let numbers = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10];;
val numbers : int list

> numbers;;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

注意，列表中的所有值必須具有相同的型別

> [1; 2; 3; 4; "cat"; 6; 7];;

  -------------^^^^^^

stdin(120,14): error FS0001: This expression has type
        string
but is here used with type
        int.

使用 :: ("cons") 運算子

[編輯 | 編輯原始碼]

使用 :: 運算子將值新增到現有列表的開頭，非常常見

> 1 :: 2 :: 3 :: [];;
val it : int list = [1; 2; 3]
注意：[] 是一個空列表。它本身的型別為 'T list；由於它與 ints 一起使用，因此它的型別為 int list。

:: 運算子將專案新增到列表的開頭，返回一個新的列表。它是一個右結合運算子，其型別如下

val inline (::) : 'T -> 'T list -> 'T list

此運算子實際上不會改變列表，而是建立一個全新的列表，將新增的元素放在開頭。以下是在 fsi 中的示例

> let x = 1 :: 2 :: 3 :: 4 :: [];;
val x : int list

> let y = 12 :: x;;
val y : int list

> x;;
val it : int list = [1; 2; 3; 4]

> y;;
val it : int list = [12; 1; 2; 3; 4]

新增元素會建立一個新的列表，但它會重用舊列表中的節點，因此新增元素是一個非常高效的 O(1) 操作。

使用 List.init

[編輯 | 編輯原始碼]

List 模組包含一個有用的方法 List.init，其型別為

val init : int -> (int -> 'T) -> 'T list

第一個引數是要建立的新列表的長度，第二個引數是生成列表中的專案的初始化函式。List.init 的使用方法如下

> List.init 5 (fun index -> index * 3);;
val it : int list = [0; 3; 6; 9; 12]

> List.init 5 (fun index -> (index, index * index, index * index * index));;
val it : (int * int * int) list
= [(0, 0, 0); (1, 1, 1); (2, 4, 8); (3, 9, 27); (4, 16, 64)]

F# 會呼叫初始化函式 5 次，每次都使用列表中每個專案的索引，從索引 0 開始。

使用列表推導式

[編輯 | 編輯原始碼]

列表推導式是指某些語言中用於生成列表的特殊語法結構。F# 具有一個表達力強的列表推導式語法，它有兩種形式：範圍和生成器。

範圍具有結構 [start .. end] 和 [start .. step .. end]。例如

> [1 .. 10];;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

> [1 .. 2 .. 10];;
val it : int list = [1; 3; 5; 7; 9]

> ['a' .. 's'];;
val it : char list
= ['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'; 'i'; 'j'; 'k'; 'l'; 'm'; 'n'; 'o';
   'p'; 'q'; 'r'; 's']

生成器具有結構 [for x in collection do ... yield expr]，並且它們比範圍靈活得多。例如

> [ for a in 1 .. 10 do
        yield (a * a) ];;
val it : int list = [1; 4; 9; 16; 25; 36; 49; 64; 81; 100]

> [ for a in 1 .. 3 do
    for b in 3 .. 7 do
        yield (a, b) ];;
val it : (int * int) list
= [(1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (2, 3); (2, 4); (2, 5); (2, 6);
   (2, 7); (3, 3); (3, 4); (3, 5); (3, 6); (3, 7)]

> [ for a in 1 .. 100 do
    if a % 3 = 0 && a % 5 = 0 then yield a];;
val it : int list = [15; 30; 45; 60; 75; 90]

可以迴圈遍歷任何集合，而不僅僅是數字。此示例迴圈遍歷一個 char list

> let x = [ 'a' .. 'f' ];;

val x : char list

> [for a in x do yield [a; a; a] ];;
val it : char list list
= [['a'; 'a'; 'a']; ['b'; 'b'; 'b']; ['c'; 'c'; 'c']; ['d'; 'd'; 'd'];
   ['e'; 'e'; 'e']; ['f'; 'f'; 'f']]

注意，yield 關鍵字將單個值推入列表。另一個關鍵字 yield! 將值的集合推入列表。yield! 關鍵字的用法如下

> [for a in 1 .. 5 do
    yield! [ a .. a + 3 ] ];;
val it : int list
= [1; 2; 3; 4; 2; 3; 4; 5; 3; 4; 5; 6; 4; 5; 6; 7; 5; 6; 7; 8]

可以混合使用 yield 和 yield! 關鍵字

> [for a in 1 .. 5 do
    match a with
    | 3 -> yield! ["hello"; "world"]
    | _ -> yield a.ToString() ];;
val it : string list = ["1"; "2"; "hello"; "world"; "4"; "5"]

替代列表推導式語法

[編輯 | 編輯原始碼]

上面的示例顯式地使用了 yield 關鍵字，但是 F# 為列表推導式提供了稍微不同的基於箭頭的語法

> [ for a in 1 .. 5 -> a * a];;
val it : int list = [1; 4; 9; 16; 25]

> [ for a in 1 .. 5 do
    for b in 1 .. 3 -> a, b];;
val it : (int * int) list
= [(1, 1); (1, 2); (1, 3); (2, 1); (2, 2); (2, 3); (3, 1); (3, 2); (3, 3);
   (4, 1); (4, 2); (4, 3); (5, 1); (5, 2); (5, 3)]

-> 分別相當於 yield 運算子。雖然使用 -> 表達列表推導式仍然很常見，但本書不會強調此結構，因為它已被棄用，取而代之的是 yield。

模式匹配列表

[編輯 | 編輯原始碼]

使用與建立列表相同的語法來匹配列表。以下是一個簡單的程式

let rec sum total = function
    | [] -> total
    | hd :: tl -> sum (hd + total) tl

let main() =
    let numbers = [ 1 .. 5 ]
    let sumOfNumbers = sum 0 numbers
    printfn "sumOfNumbers: %i" sumOfNumbers
    
main()

sum 方法的型別為 val sum : int -> int list -> int。它遞迴地列舉列表，將列表中的每個專案新增到值 total 中。該函式逐步工作，如下所示

total 輸入 hd :: tl sum (hd + total) tl
0 [1; 2; 3; 4; 5] 1 :: [2; 3; 4; 5] sum (1 + 0 = 1) [2; 3; 4; 5]
1 [2; 3; 4; 5] 2 :: [3; 4; 5] sum (2 + 1 = 3) [3; 4; 5]
3 [3; 4; 5] 3 :: [4; 5] sum (3 + 3 = 6) [4; 5]
6 [4; 5] 4 :: [5] sum (4 + 6 = 10) [5]
10 [5] 5 :: [] sum (5 + 10 = 15) []
15 [] n/a 返回 total

反轉列表

[編輯 | 編輯原始碼]

通常，我們使用遞迴和模式匹配從現有列表生成新列表。反轉列表是一個簡單的例子

let reverse l =
    let rec loop acc = function
        | [] -> acc
        | hd :: tl -> loop (hd :: acc) tl
    loop [] l
注意初學者：上面看到的模式非常常見。通常，當我們遍歷列表時，我們希望構建一個新的列表。為了遞迴地做到這一點，我們使用一個累積引數（在上面的例子中稱為 acc），它在生成新列表時儲存著新列表。使用巢狀函式也很常見，通常命名為 innerXXXXX 或 loop，以便從客戶端隱藏函式的實現細節（換句話說，客戶端不必傳遞他們自己的累積引數）。

reverse 的型別為 val reverse : 'a list -> 'a list。使用方法如下

> reverse [1 .. 5];;
val it : int list = [5; 4; 3; 2; 1]

此簡單函式之所以有效，是因為專案總是新增到累積引數 acc 的開頭，導致一系列遞迴呼叫，如下所示

acc 輸入 loop (hd :: acc) tl
[] [1; 2; 3; 4; 5] loop (1 :: []) [2; 3; 4; 5]
[1] [2; 3; 4; 5] loop (2 :: [1]) [3; 4; 5]
[2; 1] [3; 4; 5] loop (3 :: [2; 1]) [4; 5]
[3; 2; 1] [4; 5] loop (4 :: [3; 2; 1]) [5]
[4; 3; 2; 1] [5] loop (5 :: [4; 3; 2; 1]) []
[5; 4; 3; 2; 1] [] 返回 acc

List.rev 是用於反轉列表的內建函式

> List.rev [1 .. 5];;
val it : int list = [5; 4; 3; 2; 1]

過濾列表

[編輯 | 編輯原始碼]

通常，我們想要過濾列表以獲取特定值。我們可以編寫一個過濾函式，如下所示

open System

let rec filter predicate = function
    | [] -> []
    | hd :: tl ->
        match predicate hd with
        | true -> hd::filter predicate tl
        | false -> filter predicate tl

let main() =
    let filteredNumbers = [1 .. 10] |> filter (fun x -> x % 2 = 0)
    printfn "filteredNumbers: %A" filteredNumbers
    
main()

filter 方法的型別為 val filter : ('a -> bool) -> 'a list -> 'a list。上面的程式輸出

filteredNumbers: [2; 4; 6; 8; 10]

我們可以對上面的 filter 進行略微修改，使其尾遞迴

let filter predicate l =
    let rec loop acc = function
        | [] -> acc
        | hd :: tl ->
            match predicate hd with
            | true -> loop (hd :: acc) tl
            | false -> loop (acc) tl
    List.rev (loop [] l)
注意：由於累積引數通常以相反的順序構建列表，因此在從函式返回列表之前立即呼叫 List.rev 非常常見，以便將其按正確順序排列。

對映列表

[編輯 | 編輯原始碼]

我們可以編寫一個將一個列表對映到另一個列表的函式

open System

let rec map converter = function
    | [] -> []
    | hd :: tl -> converter hd::map converter tl

let main() =
    let mappedNumbers = [1 .. 10] |> map ( fun x -> (x * x).ToString() )
    printfn "mappedNumbers: %A" mappedNumbers
    
main()

map 的型別為 val map : ('a -> 'b) -> 'a list -> 'b list。上面的程式輸出

mappedNumbers: ["1"; "4"; "9"; "16"; "25"; "36"; "49"; "64"; "81"; "100"]

一個尾遞迴的 map 函式可以寫成

let map converter l =
    let rec loop acc = function
        | [] -> acc
        | hd :: tl -> loop (converter hd :: acc) tl
    List.rev (loop [] l)

與上面的例子類似，我們使用累加引數和逆序模式來使函式尾遞迴。

使用 List 模組

[編輯 | 編輯原始碼]

雖然上面已經實現了反轉、過濾和對映方法，但使用 F# 的內建函式更方便

List.rev 反轉列表

> List.rev [1 .. 5];;
val it : int list = [5; 4; 3; 2; 1]

List.filter 過濾列表

> [1 .. 10] |> List.filter (fun x -> x % 2 = 0);;
val it : int list = [2; 4; 6; 8; 10]

List.map 將一個列表從一種型別對映到另一種型別

> [1 .. 10] |> List.map (fun x -> (x * x).ToString());;
val it : string list
= ["1"; "4"; "9"; "16"; "25"; "36"; "49"; "64"; "81"; "100"]

List.append 和 @ 運算子

[編輯 | 編輯原始碼]

List.append 的型別為

val append : 'T list -> 'T list -> 'T list

正如你所料，append 函式將一個列表追加到另一個列表。@ 運算子是一箇中綴運算子，執行相同的函式

let first = [1; 2; 3;]
let second = [4; 5; 6;]
let combined1 = first @ second (* returns [1; 2; 3; 4; 5; 6] *)
let combined2 = List.append first second (* returns [1; 2; 3; 4; 5; 6] *)

由於列表是不可變的，將兩個列表連線在一起需要複製所有列表元素以建立一個全新的列表。但是，由於列表是不可變的，只需要複製第一個列表的元素；第二個列表不需要複製。在記憶體中表示，將兩個列表連線起來可以如下圖所示

我們從以下開始

   first = 1 :: 2 :: 3 :: []

   second = 4 :: 5 :: 6 :: []

將兩個列表連線起來，first @ second，得到以下結果

      first = 1 :: 2 :: 3 :: []
              \______  ______/
                     \/     
   combined = 1 :: 2 :: 3 :: second
                  (copied)

換句話說，F# 將 first 的副本附加到 second 以建立 combined 列表。這個假設可以用以下 fsi 程式碼驗證

> let first = [1; 2; 3;]
let second = [4; 5; 6;]
let combined = first @ second
let secondHalf = List.tail (List.tail (List.tail combined));;

val first : int list
val second : int list
val combined : int list
val secondHalf : int list

> System.Object.ReferenceEquals(second, secondHalf);;
val it : bool = true

兩個列表 second 和 secondHalf 在記憶體中實際上是同一個物件，這意味著 F# 在構建新列表 combined 時重用了 second 中的節點。

將兩個列表連線起來，list1 和 list2 的空間和時間複雜度為 O(list1.Length)。

List.choose

[編輯 | 編輯原始碼]

List.choose 有以下定義

val choose : ('T -> 'U option) -> 'T list -> 'U list

choose 方法很巧妙，因為它同時過濾和對映列表

> [1 .. 10] |> List.choose (fun x ->
    match x % 2 with
    | 0 -> Some(x, x*x, x*x*x)
    | _ -> None);;
val it : (int * int * int) list
= [(2, 4, 8); (4, 16, 64); (6, 36, 216); (8, 64, 512); (10, 100, 1000)]

choose 過濾返回 Some 的專案，並將它們對映到另一個值，一步完成。

List.fold 和 List.foldBack

[編輯 | 編輯原始碼]

List.fold 和 List.foldBack 有以下定義

val fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State
val foldBack : ('T -> 'State -> 'State) -> 'T list -> 'State -> 'State

“fold” 操作將函式應用於列表中的每個元素，將函式的結果聚合在一個累加器變數中，並將累加器作為 fold 操作的結果返回。'State 型別表示累積的值，它是計算一輪的輸出，也是下一輪的輸入。這個描述讓 fold 操作聽起來更復雜，但實現實際上非常簡單

(* List.fold implementation *)
let rec fold (f : 'State -> 'T -> 'State) (seed : 'State) = function
    | [] -> seed
    | hd :: tl -> fold f (f seed hd) tl
    
(* List.foldBack implementation *)
let rec foldBack (f : 'T -> 'State -> 'State) (items : 'T list) (seed : 'State) =
    match items with
    | [] -> seed
    | hd :: tl -> f hd (foldBack f tl seed)

fold 將函式從左到右應用於列表中的每個元素，而 foldBack 將函式從右到左應用於每個元素。讓我們使用以下示例更詳細地檢查 fold 函式

let input = [ 2; 4; 6; 8; 10 ]
let f accumulator input = accumulator * input
let seed = 1
let output = List.fold f seed input

output 的值為 3840。此表演示瞭如何計算 output

累加器 輸入 f 累加器 輸入 = 累加器 * 輸入
1 (種子) 2 1 * 2 = 2
2 4 2 * 4 = 8
8 6 8 * 6 = 48
48 8 48 * 8 = 384
384 10 384 * 10 = 3840 (返回值)

List.fold 將一個累加器和列表中的一個專案傳遞給一個函式。函式的輸出作為下一個專案的累加器傳遞。

如上所示，fold 函式從列表中的第一個專案到最後一個專案處理列表，或從左到右。正如你所料，List.foldBack 的工作方式相同，但它對列表的操作是從右到左。給定一個 fold 函式 f 和一個列表 [1; 2; 3; 4; 5]，fold 方法以以下方式轉換我們的列表

fold: f (f (f (f (f (f seed 1) 2) 3) 4) 5
foldBack: f 1 (f 2 (f 3(f 4(f 5 seed))))

List 模組中還有幾個與摺疊相關的其他函式

  • fold2 和 foldBack2：同時摺疊兩個列表。
  • reduce 和 reduceBack：與 fold 和 foldBack 相同，只是它使用列表中的第一個（或最後一個）元素作為種子值。
  • scan 和 scanBack：類似於 fold 和 foldBack，只是它返回所有中間值作為一個列表，而不是最終累積的值。

Fold 函式非常有用

將 1 - 100 的數字加起來 

let x = [ 1 .. 100 ] |> List.fold ( + ) 0 (* returns 5050 *)

在 F# 中，數學運算子與函式沒有區別。如上所示，我們實際上可以將加法運算子傳遞給 fold 函式，因為 + 運算子的定義為 int -> int -> int。

計算階乘 

let factorial n = [ 1I .. n ] |> List.fold ( * ) 1I
let x = factorial 13I (* returns 6227020800I *)

計算總體標準差 

let stddev (input : float list) =
    let sampleSize = float input.Length
    let mean = (input |> List.fold ( + ) 0.0) / sampleSize
    let differenceOfSquares =
        input |> List.fold
            ( fun sum item -> sum + Math.Pow(item - mean, 2.0) ) 0.0
    let variance = differenceOfSquares / sampleSize
    Math.Sqrt(variance)

let x = stddev [ 5.0; 6.0; 8.0; 9.0 ] (* returns 1.58113883 *)

List.find 和 List.tryFind

[編輯 | 編輯原始碼]

List.find 和 List.tryfind 有以下型別

val find : ('T -> bool) -> 'T list -> 'T
val tryFind : ('T -> bool) -> 'T list -> 'T option

find 和 tryFind 方法返回列表中第一個使搜尋函式返回 true 的專案。它們僅在以下方面有所不同：如果未找到滿足搜尋函式的專案，find 將丟擲一個 KeyNotFoundException，而 tryfind 將返回 None。

這兩個函式的使用方式如下

> let cities = ["Bellevue"; "Omaha"; "Lincoln"; "Papillion"; "Fremont"];;

val cities : string list =
  ["Bellevue"; "Omaha"; "Lincoln"; "Papillion"; "Fremont"]

> let findStringContaining text (items : string list) =
    items |> List.find(fun item -> item.Contains(text));;

val findStringContaining : string -> string list -> string

> let findStringContaining2 text (items : string list) =
    items |> List.tryFind(fun item -> item.Contains(text));;

val findStringContaining2 : string -> string list -> string option

> findStringContaining "Papi" cities;;
val it : string = "Papillion"

> findStringContaining "Hastings" cities;;
System.Collections.Generic.KeyNotFoundException: The given key was not present in the dictionary.
   at Microsoft.FSharp.Collections.ListModule.find[T](FastFunc`2 predicate, FSharpList`1 list)
   at <StartupCode$FSI_0007>.$FSI_0007.main@()
stopped due to error

> findStringContaining2 "Hastings" cities;;
val it : string option = None

練習

[編輯 | 編輯原始碼]

解決方案.

配對和解配對

[編輯 | 編輯原始碼]

編寫兩個函式，定義如下

val pair : 'a list -> ('a * 'a) list
val unpair : ('a * 'a) list -> 'a list

pair 函式應將列表轉換為如下所示的配對列表

pair [ 1 .. 10 ] = [(1, 2); (3, 4); (5, 6); (7, 8); (9, 10)]
pair [ "one"; "two"; "three"; "four"; "five" ] = [("one", "two"); ("three", "four")]

unpair 函式應將配對列表轉換為傳統的列表，如下所示

unpair [(1, 2); (3, 4); (5, 6)] = [1; 2; 3; 4; 5; 6]
unpair [("one", "two"); ("three", "four")] = ["one"; "two"; "three"; "four"]

展開列表

[編輯 | 編輯原始碼]

編寫一個具有以下型別定義的函式

val expand : 'a list -> 'a list list

expand 函式應按如下所示展開列表

expand [ 1 .. 5 ] = [ [1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5] ]
expand [ "monkey"; "kitty"; "bunny"; "rat" ] =
    [ ["monkey"; "kitty"; "bunny"; "rat"];
      ["kitty"; "bunny"; "rat"];
      ["bunny"; "rat"];
      ["rat"] ]

列表上的最大公約數

[編輯 | 編輯原始碼]

任務是計算一列整數的最大公約數。
第一步是編寫一個函式，其型別應如下所示

val gcd : int -> int -> int

gcd 函式應接受兩個整數並返回它們的最大公約數。提示：使用 wikipedia:Euclidean algorithm

gcd 15 25 = 5

第二步是使用 gcd 函式計算 int 列表的最大公約數。

val gcdl : int list -> int

gcdl 函式應按如下方式工作

gcdl [15; 75; 20] = 5

如果列表為空，則結果應為 0。

基本的歸併排序演算法

[編輯 | 編輯原始碼]

本練習的目標是在 F# 中實現歸併排序演算法來對列表進行排序。當我談論排序時，指的是按升序排序。如果你不熟悉歸併排序演算法，它的工作原理如下

  • 拆分：將列表分成兩個大小相等的子列表
  • 排序：對這些子列表進行排序
  • 合併：排序的同時合併（因此得名）

請注意，該演算法是遞迴工作的。它首先會拆分列表。下一步是對兩個子列表進行排序。為此，它們將再次拆分，依此類推。這將基本上持續下去，直到原始列表被完全打亂。然後，遞迴將發揮其魔力，從底部組裝列表。這在一開始可能看起來很混亂，但你會學到很多關於遞迴如何工作的知識，當涉及到多個函式時

split 函式

val split : 'a list -> 'a list * 'a list

split 函式將按如下方式工作。

split [2; 8; 5; 3] = ( [5; 2], [8; 3] )

拆分將作為元組返回。split 函式不需要對列表進行排序。

merge 函式
下一步是合併。我們現在想將拆分合併成一個排序的列表，假設兩個拆分本身已經排序。merge 函式將接收兩個已排序列表的元組，並遞迴地建立一個排序列表

val merge : 'a list * 'a list -> 'a list

示例

merge ( [2; 5], [3; 8] ) = [2; 3; 5; 8]

需要注意的是，merge 函式僅在兩個拆分已經排序的情況下才會起作用。這將簡化其實現。假設兩個拆分都已排序，我們只需檢視兩個拆分的第一個元素，並比較哪個更小。為了確保這種情況，我們將編寫最後一個函式。

msort 函式
你可以把它想象成一個組織演算法正確執行的函式。它使用之前實現的函式，因此能夠接受一個隨機列表並返回排序後的列表。

val msort : 'a list -> 'a list

如何實現 msort
如果列表為空或列表只有一個元素，我們不需要對其進行任何操作，可以直接返回它，因為我們不需要排序它。
如果不是這種情況，我們需要對其應用我們的演算法。首先將列表拆分成兩個元素的元組，然後合併元組，同時遞迴地對元組的兩個引數進行排序。

前一頁：元組和記錄 索引 下一頁：序列
摘自 "https://wikibook.tw/w/index.php?title=F_Sharp_Programming/Lists&oldid=4397721"
華夏公益教科書