Generic Equals implementation

Question

I have several generic equality functions, which are used when overriding Object.Equals:

type IEqualityComparer<'T> = System.Collections.Generic.IEqualityComparer<'T>

let equalIf f (x:'T) (y:obj) =
  if obj.ReferenceEquals(x, y) then true
  else
    match box x, y with
    | null, _ | _, null -> false
    | _, (:? 'T as y) -> f x y
    | _ -> false

let equalByWithComparer (comparer:IEqualityComparer<_>) f (x:'T) (y:obj) = 
  (x, y) ||> equalIf (fun x y -> comparer.Equals(f x, f y))

Typical usage would be:

type A(name) =
  member __.Name = name
  override this.Equals(that) = 
    (this, that) ||> equalByWithComparer StringComparer.InvariantCultureIgnoreCase (fun a -> a.Name)

type B(parent:A, name) =
  member __.Parent = parent
  member __.Name = name
  override this.Equals(that) = (this, that) ||> equalIf (fun x y ->
    x.Parent.Equals(y.Parent) && StringComparer.InvariantCultureIgnoreCase.Equals(x.Name, y.Name))

I'm mostly happy with this. It reduces boilerplate^[wikipedia]. But I'm annoyed having to use equalBy instead of the more concise equalByWithComparer in type B (since its equality depends on its parent's).

It feels like it should be possible to write a function that accepts a reference to the parent (or 0..N projections), which are checked for equality using Equals, along with a property to be checked and its accompanying comparer, but I've yet been unable imagine its implementation. Perhaps all this is overdone (not sure). How might such a function be implemented?

EDIT

Based on Brian's answer, I came up with this, which seems to work okay.

let equalByProjection proj (comparer:IEqualityComparer<_>) f (x:'T) (y:obj) = 
  (x, y) ||> equalIf (fun x y -> 
    Seq.zip (proj x) (proj y)
    |> Seq.forall obj.Equals && comparer.Equals(f x, f y))

type B(parent:A, otherType, name) =
  member __.Parent = parent
  member __.OtherType = otherType //Equals is overridden
  member __.Name = name
  override this.Equals(that) = 
    (this, that) ||> equalByProjection
      (fun x -> [box x.Parent; box x.OtherType])
      StringComparer.InvariantCultureIgnoreCase (fun b -> b.Name)

Answer 1

Are you just looking for something that takes e.g.

[
    (fun x -> x.Parent), (fun a b -> a.Equals(b))
    (fun x -> x.Name), (fun a b -> SC.ICIC.Equals(a,b))
]

where you have the list of (projection x comparer) to run on the object? (Probably will need more type annotations, or clever pipelining.)

Answer 2

Another implementation, based on Brian's suggestion:

open System
open System.Collections.Generic

// first arg is always 'this' so assuming that it cannot be null
let rec equals(a : 'T, b : obj) comparisons = 
    if obj.ReferenceEquals(a, b) then true
    else 
        match b with
        | null -> false
        | (:? 'T as b) -> comparisons |> Seq.forall(fun c -> c a b)
        | _ -> false

// get values and compares them using obj.Equals 
//(deals with nulls in both positions then calls <first arg>.Equals(<second arg>))
let Eq f a b = obj.Equals(f a, f b) 
// get values and compares them using IEqualityComparer
let (=>) f (c : IEqualityComparer<_>) a b = c.Equals(f a, f b)

type A(name) =
  member __.Name = name
  override this.Equals(that) = 
    equals (this, that) [
        (fun x -> x.Name) => StringComparer.InvariantCultureIgnoreCase
        ]

type B(parent:A, name) =
  member __.Parent = parent
  member __.Name = name
  override this.Equals(that) = 
    equals(this, that) [
        Eq(fun x -> x.Parent)
        (fun x -> x.Name) => StringComparer.InvariantCultureIgnoreCase
    ]

Answer 3

Just to satisfy Daniel's curiosity, here's how to encode the existential type

exists 'p. ('t -> 'p) * ('p -> 'p -> bool)

in F#. Please don't up-vote this answer! It's too ugly to recommend in practice.

The basic idea is that the existential type above is roughly equivalent to

forall 'x. (forall 'p. ('t -> 'p) * ('p -> 'p -> bool) -> 'x) -> 'x

because the only way that we could implement a value of this type is if we really have an instance of ('t -> 'p) * ('p -> 'p -> bool) for some 'p that we can pass to the first argument to get out a return value of the arbitrary type 'x.

Although it looks more complicated than the original type, this latter type can be expressed in F# (via a pair of nominal types, one for each forall):

type ProjCheckerUser<'t,'x> =
    abstract Use : ('t -> 'p) * ('p -> 'p -> bool) -> 'x
type ExistsProjChecker<'t> =
    abstract Apply : ProjCheckerUser<'t,'x> -> 'x

// same as before
let equalIf f (x:'T) (y:obj) =               
    if obj.ReferenceEquals(x, y) then true               
    else               
    match box x, y with               
    | null, _ | _, null -> false               
    | _, (:? 'T as y) -> f x y               
    | _ -> false      

let checkAll (l:ExistsProjChecker<_> list) a b =
    // with language support, this could look more like:
    // let checkProj (ExistsProjChecker(proj,check)) = check (proj a) (proj b)
    // l |> List.forall checkProj
    let checkProj = {new ProjCheckerUser<_,_> with 
                        member __.Use(proj,check) = check (proj a) (proj b) }
    l |> List.forall 
            (fun ex -> ex.Apply checkProj)

let fastIntCheck (i:int) j = (i = j)
let fastStringCheck (s:string) t = (s = t)

type MyType(id:int, name:string) =
    static let checks = 
        // with language support this could look more like:
        // [ExistsProjChecker((fun (t:MyType) -> t.Id, fastIntCheck)
        //  ExistsProjChecker((fun (t:MyType) -> t.Name, fastStringCheck)]
        [{ new ExistsProjChecker<MyType> with 
               member __.Apply u = u.Use ((fun t -> t.Id), fastIntCheck)    }
         { new ExistsProjChecker<MyType> with 
               member __.Apply u = u.Use ((fun t -> t.Name), fastStringCheck) }]
    member x.Id = id
    member x.Name = name
    override x.Equals(y) =
        equalIf (checkAll checks) x y

As you can see, the lack of language support results in a lot of boilerplate (basically all of the object creation expressions, calls the the method Use and Apply), which makes this approach unattractive.