mutable dictionary immutable in F#

Question

I have code that declares a mutable dictionary but I will get an error when I try to change an element.

The code:

   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

this creates an IDictionary. I understand that the object itself is immutable but the contents of the dictionary should be mutable.

When I change the code by explicitly initializing the dictionary then it becomes mutable:

   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

Why is that?

Answer 1

IDictionary is an interface, not a class. This interface may have multiple different implementations. You can even make one yourself.

Dictionary is indeed one of these implementations. It supports the full functionality of the interface.

But that's not the implementation that the dict function returns. Let's try this:

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

Turns out the implementation that the dict function returns is Microsoft.FSharp.Core.ExtraTopLevelOperators.DictImpl - a class named DictImpl defined deep in the innards of the F# standard library.

And it just so happens that certain methods on that interface throw a NotSupportedException:

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

That's by design. It's done this way on purpose, to support "immutability by default".

If you really want to have a mutable version, you can create a copy by using one of Dictionary's constructors:

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

---

The difference between Map and Dictionary is the implementation, which then implies memory and runtime characteristics.

Dictionary is a hashtable. It offers constant-time insertion and retrieval, but to pay for that it relies on consistent hashing of its keys and its updates are destructive, which also comes with thread-unsafety.

Map is implemented as a tree. It offers logarithmic insertion and retrieval, but in return has the benefits of a persistent data structure. Also, it requires keys to be comparable. Try this:

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

Comparing keys is essential for building a tree.

Answer 2

The difference is that dict is a read-only dictionary with some mutating methods that throw an exception (which is a disadvantage of that type), whereas the map is an immutable collection that uses functions from the Map module as well as methods to modify elements of the map and return a copy. There is a good explanation of this in Lesson 17 of the book Get Programming with F#.

Also, for the dict, "Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table." from the docs; whereas the map is based on a binary tree, so retrieving a value by using its key has O(log(N)) complexity. See Collection Types. This also means that the keys in a map are ordered; whereas in a dict, they are unordered.

For many use cases, the difference in performance would be negligible, so the default choice for Functional Programming style should be the map, since its programming interface is similar in style to the other F# collections like list and seq.