Reputation: 12137
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?
Upvotes: 5
Views: 1082
Reputation: 1721
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
.
Upvotes: 2
Reputation: 80915
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.
Upvotes: 6
Reputation: 6324
dict
is a helper method to create an iDictionary
, this dictionary is immutable (so you need to supply the contents during the creation of the object). It is actually a read-only dictionary so no surprise that you cannot modify its contents. In your second example you explicitly create a Dictionary
which is a mutable dictionary. Since Dictionary can take a iDictionary you could just pass in your iDictionary to it.
Upvotes: 0