F# 程式設計/集合和對映

F# : 集合和對映

除了列表和序列，F# 還提供了兩種相關的不可變資料結構，稱為集合和對映。與列表不同，集合和對映是無序的資料結構，這意味著這些集合不會保留元素插入時的順序，也不允許重複項。

集合

F# 中的集合只是一個用於存放專案的容器。集合不會保留插入專案的順序，也不允許在集合中插入重複項。

集合可以透過多種方式建立

向空集合新增專案 Set 模組包含一個有用的函式 Set.empty，它返回一個空集合作為起點。

方便的是，所有集合例項都具有一個 Add 函式，其型別為 val Add : 'a -> Set<'a>。換句話說，我們的 Add 返回一個包含新專案的新集合，這使得以這種方式將專案新增到一起變得容易

> Set.empty.Add(1).Add(2).Add(7);;
val it : Set<int> = set [1; 2; 7]

將列表和序列轉換為集合 此外，我們可以使用 Set.ofList 和 Set.ofSeq 將整個集合轉換為集合

> Set.ofList ["Mercury"; "Venus"; "Earth"; "Mars"; "Jupiter"; "Saturn"; "Uranus"; "Neptune"];;
val it : Set<string> = set ["Earth"; "Jupiter"; "Mars"; "Mercury"; ...]

上面的示例演示了集合的無序特性。

集合模組

在 FSharp.Collections.Set 模組中包含了各種用於處理集合的有用方法。

val add : 'a -> Set<'a> -> Set<'a>

返回一個新的集合，其中包含已新增到集合中的元素。如果集合已經包含給定元素，則不會引發異常。

val compare : Set<'a> -> Set<'a> -> int

比較兩個集合。將集合放入總順序。

val count : Set<'a> -> int

返回集合中的元素數量。與“大小”相同。

val difference : Set<'a> -> Set<'a> -> Set<'a>

返回一個新的集合，其中包含從第一個集合中刪除了第二個集合的元素。即一個只包含第一個集合中不在第二個集合中的專案的集合。

> let a = Set.ofSeq [ 1 .. 10 ]
let b = Set.ofSeq [ 5 .. 15 ];;

val a : Set<int>
val b : Set<int>

> Set.difference a b;;
val it : Set<int> = set [1; 2; 3; 4]

> a - b;; (* The '-' operator is equivalent to Set.difference *)
val it : Set<int> = set [1; 2; 3; 4]

val exists : ('a -> bool) -> Set<'a> -> bool

測試集合中是否有任何元素滿足給定的謂詞。

val filter : ('a -> bool) -> Set<'a> -> Set<'a>

返回一個新的集合，該集合僅包含給定謂詞返回“true”的集合中的元素。

val intersect : Set<'a> -> Set<'a> -> Set<'a>

計算兩個集合的交集或重疊部分。

> let a = Set.ofSeq [ 1 .. 10 ]
let b = Set.ofSeq [ 5 .. 15 ];;

val a : Set<int>
val b : Set<int>

> Set.iter (fun x -> printf "%O " x) (Set.intersect a b);;
5 6 7 8 9 10

val map : ('a -> 'b) -> Set<'a> -> Set<'b>

返回一個新的集合，其中包含將給定函式應用於輸入集合的每個元素的結果。

val contains: 'a -> Set<'a> -> bool

如果給定元素在給定集合中，則計算結果為 true。

val remove : 'a -> Set<'a> -> Set<'a>

返回一個新的集合，其中已刪除給定元素。如果集合不包含給定元素，則不會引發異常。

val count: Set<'a> -> int

返回集合中的元素數量。

val isSubset : Set<'a> -> Set<'a> -> bool

如果第一個集合的所有元素都在第二個集合中，則計算結果為“true”。

val isProperSubset : Set<'a> -> Set<'a> -> bool

如果第一個集合的所有元素都在第二個集合中，並且第二個集合中至少有一個元素不在第一個集合中，則計算結果為“true”。

> let a = Set.ofSeq [ 1 .. 10 ]
let b = Set.ofSeq [ 5 .. 15 ]
let c = Set.ofSeq [ 2; 4; 5; 9 ];;

val a : Set<int>
val b : Set<int>
val c : Set<int>

> Set.isSubset c a;; (* All elements of 'c' exist in 'a' *)
val it : bool = true

> Set.isSubset c b;; (* Not all of the elements of 'c' exist in 'b' *);;
val it : bool = false

val union : Set<'a> -> Set<'a> -> Set<'a>

計算兩個集合的並集。

> let a = Set.ofSeq [ 1 .. 10 ]
let b = Set.ofSeq [ 5 .. 15 ];;

val a : Set<int>
val b : Set<int>

> Set.iter (fun x -> printf "%O " x) (Set.union a b);;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 val it : unit = ()

> Set.iter (fun x -> printf "%O " x) (a + b);; (* '+' computes union *)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

示例

open System

let shakespeare = "O Romeo, Romeo! wherefore art thou Romeo?"
let shakespeareArray =
    shakespeare.Split([| ' '; ','; '!'; '?' |], StringSplitOptions.RemoveEmptyEntries)
let shakespeareSet = shakespeareArray |> Set.ofSeq
    
let main() =
    printfn "shakespeare: %A" shakespeare
    
    let printCollection msg coll =
        printfn "%s:" msg
        Seq.iteri (fun index item -> printfn "  %i: %O" index item) coll
        
    printCollection "shakespeareArray" shakespeareArray
    printCollection "shakespeareSet" shakespeareSet
    
    Console.ReadKey(true) |> ignore
            
main()

shakespeare: "O Romeo, Romeo! wherefore art thou Romeo?"
shakespeareArray:
  0: O
  1: Romeo
  2: Romeo
  3: wherefore
  4: art
  5: thou
  6: Romeo
shakespeareSet:
  0: O
  1: Romeo
  2: art
  3: thou
  4: wherefore

對映

對映是一種特殊的集合：它將鍵與值關聯起來。對映的建立方式與集合類似

> let holidays =
    Map.empty. (* Start with empty Map *)
        Add("Christmas", "Dec. 25").
        Add("Halloween", "Oct. 31").
        Add("Darwin Day", "Feb. 12").
        Add("World Vegan Day", "Nov. 1");;

val holidays : Map<string,string>

> let monkeys =
    [ "Squirrel Monkey", "Simia sciureus";
        "Marmoset", "Callithrix jacchus";
        "Macaque", "Macaca mulatta";
        "Gibbon", "Hylobates lar";
        "Gorilla", "Gorilla gorilla";
        "Humans", "Homo sapiens";
        "Chimpanzee", "Pan troglodytes" ]
    |> Map.ofList;; (* Convert list to Map *)

val monkeys : Map<string,string>

您可以使用 .[key] 訪問對映中的元素

> holidays.["Christmas"];;
val it : string = "Dec. 25"

> monkeys.["Marmoset"];;
val it : string = "Callithrix jacchus"

對映模組

在 FSharp.Collections.Map 模組中處理對映操作。

val add : 'key -> 'a -> Map<'key,'a> -> Map<'key,'a>

返回一個新的對映，其中包含已新增到給定對映中的繫結。

val empty<'key,'a> : Map<'key,'a>

返回一個空對映。

val exists : ('key -> 'a -> bool) -> Map<'key,'a> -> bool

如果給定謂詞對於對映中的一個繫結返回 true，則返回 true。

val filter : ('key -> 'a -> bool) -> Map<'key,'a> -> Map<'key,'a>

構建一個新的對映，該對映只包含給定謂詞返回 true 的繫結。

val find : 'key -> Map<'key,'a> -> 'a

在對映中查詢元素，如果對映中不存在繫結，則引發 KeyNotFoundException。

val containsKey: 'key -> Map<'key,'a> -> bool

測試元素是否在對映的域中。

val remove : 'key -> Map<'key,'a> -> Map<'key,'a>

從對映的域中刪除一個元素。如果元素不存在，則不會引發異常。

val tryFind : 'key -> Map<'key,'a> -> 'a option

在對映中查詢元素，如果元素在對映的域中，則返回 Some 值，否則返回 None。

示例

open System

let capitals =
    [("Australia", "Canberra"); ("Canada", "Ottawa"); ("China", "Beijing");
        ("Denmark", "Copenhagen"); ("Egypt", "Cairo"); ("Finland", "Helsinki");
        ("France", "Paris"); ("Germany", "Berlin"); ("India", "New Delhi");
        ("Japan", "Tokyo"); ("Mexico", "Mexico City"); ("Russia", "Moscow");
        ("Slovenia", "Ljubljana"); ("Spain", "Madrid"); ("Sweden", "Stockholm");
        ("Taiwan", "Taipei"); ("USA", "Washington D.C.")]
    |> Map.ofList

let rec main() =
    Console.Write("Find a capital by country (type 'q' to quit): ")
    match Console.ReadLine() with
    | "q" -> Console.WriteLine("Bye bye")
    | country ->
        match capitals.TryFind(country) with
        | Some(capital) -> Console.WriteLine("The capital of {0} is {1}\n", country, capital)
        | None -> Console.WriteLine("Country not found.\n")
        main() (* loop again *)
            
main()

Find a capital by country (type 'q' to quit): Egypt
The capital of Egypt is Cairo

Find a capital by country (type 'q' to quit): Slovenia
The capital of Slovenia is Ljubljana

Find a capital by country (type 'q' to quit): Latveria
Country not found.

Find a capital by country (type 'q' to quit): USA
The capital of USA is Washington D.C.

Find a capital by country (type 'q' to quit): q
Bye bye

集合和對映的效能

F# 集合和對映實現為不可變 AVL 樹，這是一種高效的資料結構，它形成一個自平衡二叉樹。AVL 樹以其效率而聞名，它們可以在 O(log n) 時間內搜尋、插入和刪除樹中的元素，其中 n 是樹中的元素數量。