當從 C# 世界遷移到 F#(最慣用的可能)思維方式時,我發現了這個有趣的差異。在 C# 的 OOP&mutable 世界中,默認的集合集合似乎是HashSet,默認情況下它似乎沒有排序(因為它接受的比較器只是為了相等);而如果你想要一個排序的,則必須使用SortedSet。然而在 F# 的世界中,基本set已經排序了,因為它需要用于實現相等和比較的元素類型。這有什么具體原因嗎?為什么不在該語言的主要集合中設置無序集合?作為旁注,我想知道是否有可能有一個不允許重復的集合,但在丟棄某些元素作為重復項時,它比某些元素具有優先權。示例:一條記錄,{ Name: string; Flag: Option<unit> }以便在插入時{ Name = "foo"; Flag = None }和稍后{ Name = "foo"; Flag = Some() }它最終僅包含后一個元素(因為存在 Flag)。
1 回答
米脂
TA貢獻1836條經驗 獲得超3個贊
F#Set恰好是排序的,但它更多的是由底層數據結構的選擇產生的實現細節,通常不應依賴。
F# 集和映射基于 AVL 樹的變體,該結構恰好保持了存儲在樹中的元素已排序的不變性。之所以需要比較約束,是因為這種樹結構中的查找依賴于元素之間的直接比較來選擇遍歷的子樹。
然而,這些結構的賣點是,它們可以用來以低廉的成本實現相當高效、不可變的映射和集合版本,而這正是 F# 在更廣泛的 .NET 平臺不提供任何替代方案的情況下所需要的。
請注意,這并不是這種情況下唯一可行的選擇,并且像 Clojure 或 Scala 這樣的 JVM 函數式語言選擇了不同的數據結構作為其映射的基礎 - 哈希數組映射 trie - 這也是不可變和持久的,可以說實現起來更復雜,對于較大的集合大小來說可以說更有效,但碰巧存儲無序的元素。與AVL樹不同,樹的遍歷是基于哈希的,因此不需要比較約束。
因此,如果您已經知道您的優先級是不變性,那么排序集實際上比未排序集更容易實現。
- 1 回答
- 0 關注
- 146 瀏覽
添加回答
舉報
0/150
提交
取消
