可变字典与F#中的不可变字典

Question

可变字典与F#中的不可变字典

5

我有一段声明可变字典的代码，但当我尝试更改其中一个元素时会出错。

代码如下：

   let layers =
        seq {
            if recipes.ContainsKey(PositionSide.Short) then yield! buildLayerSide recipes.[PositionSide.Short]
            if recipes.ContainsKey(PositionSide.Long)  then yield! buildLayerSide recipes.[PositionSide.Long]
        }
        |> Seq.map (fun l -> l.Id, l)
        |> dict

这里创建了一个 IDictionary。我理解对象本身是不可变的，但字典的内容应该是可变的。

当我通过显式初始化字典来更改代码时，它就变成可变的：

   let layers =
        let a =
            seq {
                if recipes.ContainsKey(PositionSide.Short) then yield! buildLayerSide recipes.[PositionSide.Short]
                if recipes.ContainsKey(PositionSide.Long)  then yield! buildLayerSide recipes.[PositionSide.Long]
            }
            |> Seq.map (fun l -> l.Id, l)
            |> dict
    let x = Dictionary<string, Layer>()
    a
    |> Seq.iter (fun kvp -> x.[kvp.Key] <- kvp.Value)

    x

为什么会这样呢？

- Thomas

3个回答

2

区别在于 dict 是只读的字典，具有一些会抛出异常的变异方法（这是该类型的缺点），而 map 是不可变集合，它使用 Map 模块中的函数以及修改映射元素并返回副本的方法。在书籍《Get Programming with F#》的第17课中有很好的解释。

此外，对于 dict，“通过使用其键检索值非常快，接近 O(1)，因为 Dictionary 类被实现为哈希表。”来自文档；而 map 基于二叉树，因此通过使用其键检索值的复杂度为O(log(N))。请参见Collection Types。这也意味着 map 中的键是有序的；而在 dict 中，它们是无序的。

对于许多用例，性能差异可以忽略不计，因此函数式编程风格的默认选择应该是 map，因为它的编程接口与其他 F# 集合（如 list 和 seq）的风格类似。

- Scott Hutchinson

0

dict 是一个帮助方法，用于创建一个 iDictionary，这个字典是不可变的（所以你需要在对象创建时提供内容）。它实际上是一个只读字典，因此无法修改其内容。在您的第二个示例中，您明确创建了一个可变字典 Dictionary。由于 Dictionary 可以接受 iDictionary，因此您可以将 iDictionary 直接传递给它。

- s952163

我以为Map是F#中不可变的字典？ - Thomas

如果它们都生成一个不可变字典，那么在创建结束时使用 |> dict 还是 |> Map 有什么区别呢？ - Thomas

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Fyodor Soikin · Accepted Answer

IDictionary 是一个接口而不是类，这个接口可能有多个不同的实现。你甚至可以自己创建一个实现。

Dictionary 就是其中之一，它支持接口的全部功能。

但这并不是 dict 函数返回的实现。让我们来尝试一下：

> let d = dict [(1,2)]
> d.GetType().FullName
"Microsoft.FSharp.Core.ExtraTopLevelOperators+DictImpl`3[...

原来，dict 函数返回的实现是 Microsoft.FSharp.Core.ExtraTopLevelOperators.DictImpl，这是 F# 标准库深处定义的名为 DictImpl 的类。

而且恰巧在该接口上的某些方法会抛出 NotSupportedException：

> d.Add(4,5)
System.NotSupportedException: This value cannot be mutated

这是有意为之的设计。这样做是为了支持"默认不可变性(immutability by default)"。

如果您真的想要一个可变版本，可以使用其中一个Dictionary的构造函数创建一个副本：

> let m = Dictionary(d)
> m.Add(4,5)  // Works now

Map和Dictionary的区别在于实现方式，这就意味着它们的内存和运行时特性也不同。

Dictionary是一个哈希表，提供常数级别的插入和检索，但为此需要对其键进行一致的哈希，并且它的更新是破坏性的，这也导致它不安全。

Map则是以树的形式实现的，提供对数级别的插入和检索，并具有持久化数据结构的优点。此外，它要求键可比较。可以尝试以下操作：

> type Foo() = class end
> let m = Map [(Foo(), "bar")]
error FS0001: The type 'Foo' does not support the 'comparison' constraint

比较键值对于构建树结构至关重要。