Override comparison for F# set

Question

Is there any way to override the comparison function in a F# set?

I don't see any set construction functions that take a IComparer<T> or comparison function:

• Set.ofSeq et al don't take a comparison function
• FSharpSet(IComparer<T> comparer, SetTree<T> tree) constructor is internal, because
• SetTree is internal and
• SetTreeModule.ofSeq<a>(IComparer<a> comparer, IEnumerable<a> c) is obviously internal too.

My actual problem is that I have a set of ('a * 'a) and I want a comparison such that for example (1,3) = (3,1).

I know I could wrap this in a type implementing IComparable<T>, but is there any way to avoid this?

Answer 1

I think the set type available in F# core libraries doesn't allow specifying your own comparison. However, there is a tagged version of the type in PowerPack that allows this. The following shows how to create a set with comparer that compares integers using modulo 10:

#r @"FSharp.PowerPack.dll"
open System.Collections.Generic
open Microsoft.FSharp.Collections.Tagged

type MyComparer() = 
  interface IComparer<int> with
    member x.Compare(a, b) = (a % 10).CompareTo(b % 10)

// Type alias for a set that uses 'MyComparer'
type MySet = Tagged.Set<int, MyComparer>

let comparer = new MyComparer()
let s1 = MySet.Create(comparer, [1; 2; 3])
let s2 = MySet.Create(comparer, [11; 14])

MySet.Union(s1, s2)

Answer 2

You need to use a "wrapper" type as you suggest.

(For immutable types like F# Set and Map, there are API issues with custom comparators. Since each operation returns e.g. a new Set object, the new object needs to share the comparer (possibly leading to threading issues), and there is no good way to decide what comparer the result should use for e.g. the result of Set.union of two sets with different comparers. So Set and Map avoid the confusion here by always using comparison directly on the element type. As Tomas mentions, the PowerPack has an alternative API that makes the comparer part of the type, which enables a typesafe/compare-safe Union method, for instance.)

Answer 3

I had a similar problem. I was also restricted to use only the standard libraries and no external dependencies. At the same time I wanted to make use of existing implementations of the IEqualityComparer and the IComparer interfaces which I already had in hand.

So, I ended up making my own wrapper struct that I can now use with the F#'s built-in Map and Set:

open System

[<Struct>]
[<CustomComparison>]
[<CustomEquality>]
type ComparisonAdapter<'T>(value: 'T, comparer: IComparer<'T>, eqComparer: IEqualityComparer<'T>) =
    new(value) = ComparisonAdapter(value, Comparer<'T>.Default, EqualityComparer<'T>.Default)
    member this.CompareTo (cmp: IComparer<'T>, v: 'T) = cmp.Compare(v, value)
    member this.CompareTo (v: 'T) = this.CompareTo(comparer, v)
    member this.CompareTo (c: ComparisonAdapter<'T>) = c.CompareTo(comparer, value)
    member this.CompareTo (o: obj) = 
        match o with
        | :? ComparisonAdapter<'T> as ca -> this.CompareTo(ca)
        | :? 'T as t -> this.CompareTo(t)
        | :? IComparable as cmp -> (-1)*(cmp.CompareTo(value))
        | _ -> raise (NotSupportedException ())
    member this.Equals (c: ComparisonAdapter<'T>): bool = c.Equals(eqComparer, value)
    member this.Equals (cmp: IEqualityComparer<'T>, v: 'T): bool = cmp.Equals(v, value)
    member this.Equals (v: 'T): bool = eqComparer.Equals(v, value)
    override this.Equals (o: obj): bool =
        if (o :? ComparisonAdapter<'T>) then this.Equals(downcast o: ComparisonAdapter<'T>)
        else if (o :? 'T) then this.Equals(downcast o: 'T)
        else false
    override this.GetHashCode () = eqComparer.GetHashCode value
    member this.Value with get () = value
    interface IEquatable<'T> with member this.Equals other = this.Equals(eqComparer, other)
    interface IComparable<'T> with member this.CompareTo other = this.CompareTo(comparer, other)
    interface IComparable with member this.CompareTo o = this.CompareTo o

The way I use it is to create a wrapper of the built-in collection and internally create the key/item wrapper in order to make the user code more friendly. So I would have something like

type MyCustomMap<'TKey, 'TValue>(cmp: IComparer<'TKey>, eq: IEqualityComparer<'TKey>) = 
    let innerMap = new Map<ComparisonAdapter<'TKey>, 'TValue>()
    member this Add key value = 
        let actualKey = new ComparisonAdapter<'TKey>(key, cmp, eq)
        innerMap.Add actualKey value
    // * other map manipulation members omitted for brevity *

You could also use the existing map and set but you have to create the adapter for each key when you call the respective Add/Remove/TryFind and so on methods. I prefer to use a collection wrapper like the above instead, because this guarantees that each key will have the same comparer implementations and user code cannot tamper with them.