Type extension errors for Dictionary<'K, 'V>

The following type extension

module Dict =

  open System.Collections.Generic

  type Dictionary<'K, 'V> with
    member this.Difference(that:Dictionary<'K, 'T>) =
      let dict = Dictionary()
      for KeyValue(k, v) in this do
        if not (that.ContainsKey(k)) then
          dict.Add(k, v)
      dict

gives the error:

The signature and implementation are not compatible because the declaration of the type parameter 'TKey' requires a constraint of the form 'TKey : equality

But when I add the constraint it gives the error:

The declared type parameters for this type extension do not match the declared type parameters on the original type 'Dictionary<,>'

This is especially mysterious because the following type extension doesn't have the constraint and works.

type Dictionary<'K, 'V> with
  member this.TryGet(key) =
    match this.TryGetValue(key) with
    | true,开发者_运维百科 v -> Some v
    | _ -> None

Now I'm having weird thoughts: is the constraint required only when certain members are accessed?

module Dict =

  open System.Collections.Generic

  type Dictionary<'K, 'V> with
    member this.Difference(that:Dictionary<'K, 'T>) =
        let dict = Dictionary(this.Comparer)
        for KeyValue(k, v) in this do
            if not (that.ContainsKey(k)) then
                dict.Add(k, v)
        dict

EDIT:

As per F# spec (14.11 Additional Constraints on CLI Methods)

Some specific CLI methods and types are treated specially by F#, because they are common in F# programming and cause extremely difficult-to-find bugs. For each use of the following constructs, the F# compiler imposes additional ad hoc constraints:

• x.Equals(yobj) requires type ty : equality for the static type of x
• x.GetHashCode() requires type ty : equality for the static type of x
• new Dictionary<A,B>() requires A : equality, for any overload that does not take an IEqualityComparer<T>

as far as I can see the following code does the trick:

module Dict =
open System.Collections.Generic

type Dictionary<'K, 'V> with
    member this.Difference(that: Dictionary<'K,'V2>) = 
        let diff =
            this
            |> Seq.filter (fun x -> not <| that.ContainsKey(x.Key))
            |> Seq.map (fun x -> x.Key, x.Value)
        System.Linq.Enumerable.ToDictionary(diff, fst, snd)

The problem is your use of the Add method. If you use this method of Dictionary<TKey, TValue> then F# will enforce that TKey has the equality constraint.

After playing around a bit I'm not sure that it's even possible to write this extension method. The F# type system appears to force the declaration type of the extension method to have no additional constraints than the original type (i get an error whenever I add the equality constraint). Additionally the type listed in the individal extension methods cannot differ than the listed type. I've tried a number of ways and can't get this to function correctly.

The closest I've come is the non-extension method as follows

let Difference (this : Dictionary<'K, 'T>) (that:Dictionary<'K, 'T> when 'K : equality) =
    let dict = Dictionary()
    for KeyValue(k, v) in this do
        if not (that.ContainsKey(k)) then
            dict.Add(k, v)
    dict

Perhaps another F# ninja will be able to prove me wrong

(EDIT: CKoenig has a nice answer.)

Hm, I didn't immediately see a way to do this either.

Here's a non-type-safe solution that might provide some crazy inspiration for others.

open System.Collections.Generic  

module Dict =  
  type Dictionary<'K, 'V> with    
    member this.Difference<'K2, 'T when 'K2 : equality>(that:Dictionary<'K2, 'T>) =      
        let dict = Dictionary<'K2,'V>()      
        for KeyValue(k, v) in this do        
            if not (that.ContainsKey(k |> box |> unbox)) then          
                dict.Add(k |> box |> unbox, v)      
        dict

open Dict

let d1 = Dictionary()
d1.Add(1, "foo")
d1.Add(2, "bar")

let d2 = Dictionary()
d2.Add(1, "cheese")

let show (d:Dictionary<_,_>) =
    for (KeyValue(k,v)) in d do
        printfn "%A: %A" k v

d1.Difference(d2) |> show

let d3 = Dictionary()
d3.Add(1, 42)

d1.Difference(d3) |> show

let d4 = Dictionary()
d4.Add("uh-oh", 42)

d1.Difference(d4) |> show  // blows up at runtime

Overall it seems like there may be no way to unify the types K and K2 without also forcing them to have the same equality constraint though...

(EDIT: seems like calling into .NET which is equality-constraint-agnostic is a good way to create a dictionary in the absence of the extra constraint.)