跳转到内容

F# 编程/集合和映射

Add links
来自维基教科书，开放的书籍，开放的世界
上一页: 序列 索引 下一页: 判别联合
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 是树中的元素数量。

上一页: 序列 索引 下一页: 判别联合
检索自 "https://wikibooks.cn/w/index.php?title=F_Sharp_Programming/Sets_and_Maps&oldid=3809277"
华夏公益教科书