Equality and Comparison Constraints in F#
F# 1.9.7 introduces two new constraints to the F# language to help uncover issues in your code when using equality and comparison operators. In this blog entry we'll take a look at these constraints in a bit more detail. The topics in this blog post are
Tuples, Lists and other Structural Types
The Basic Equality and Comparison Operations in F#
What do the equality and comparison constraints mean?
Defining New Structural Types
Customizing Equality and Comparison
Safer Code: Suppressing Equality and Comparison on a Type
Safer Code: Safer Sets and Maps
Safer Code: Declaring Conditions for Equality over Container Types
Getting IEqualityComparer<’T> and IComparer<’T> Implementations which use F# Generic Equality
Using unchecked equality and comparison
Design Alternatives. Could interface constraints suffice? User defined constraints?
Summary
You can also find the details in the draft F# Language Specification, where similar material is covered. First, as usual, some background.
Tuples, Lists and other Structural Types
Functional programming in F# frequently involves the use of structural equality, hashing and comparison. For example:
(1,1+1) = (1,2)
will return true, because tuple types support "structural" equality. Likewise these two function calls return identical values:
hash (1,1+1)
hash (1,2)
Likewise an ordering on parts of a tuple induces an ordering on tuples themselves, so all the following evaluate to true:
(1,2) < (1,3)
(1,2) < (2,3)
(1,2) < (2,1)
(1,2) > (1,0)
The same applies to lists, options, arrays and user-defined record, union and struct types whose constituent field types permit structural equality, hashing and comparison.
Equality and comparison are a surprisingly important part of the experience of “programming with functional data” – it is difficult to imagine F# being F# if you can’t compare tuples for equality, or lists for equality, and likewise for other user-defined structural types. In each case, the behaviour of these operations depends on the equality properties of the constituent components.
This in turn means that the “idea” of equality, hashing and comparison (including structural versions of these) is built in quite deeply into the F# language and core library – for example, several pages of the F# specification are devoted to defining what happens when you use equality with user-defined structural types.
The Basic Equality and Comparison Operations in F#
Let’s take a look at the signatures of the equality, comparison and hashing operations in the F# library:
(=) : 'T -> 'T -> bool when 'T : equality
(<>) : 'T -> 'T -> bool when 'T : equality
hash : 'T -> int when 'T : equality
(<) : 'T -> 'T -> bool when 'T : comparison
(<=) : 'T -> 'T -> bool when 'T : comparison
(>) : 'T -> 'T -> bool when 'T : comparison
(>=) : 'T -> 'T -> bool when 'T : comparison
compare : 'T -> 'T -> int when 'T : comparison
min : 'T -> 'T -> 'T when 'T : comparison
max : 'T -> 'T -> 'T when 'T : comparison
First note that these are generic operations – they can be used on objects of many different types. This can be seen by the use of 'T in the signatures of these operations. These operations take one or two parameters of the same type. For example, you can apply the “=” operator to two Form objects, or two System.DateTime objects, or two System.Type objects, and something reasonable will happen. Some other important derived generic types such as the immutable (persistent) Set<_> and Map<_,_> types in the F# library also use generic comparison on their key type:
type Set<'T when 'T : comparison> = ...
type Map<'Key, 'Value when 'Key : comparison> = ...
In common with many other basic generic operators in the F# library, the above operations are constrained, in this case by the 'T : equality and 'T : comparison constraints. The purpose of constraints on type parameters is to make sure the operations are only used on a reasonable set of types. For example, consider using equality and comparison on a System.Windows.Forms.Form object. Equality is permitted, because the default for nearly all .NET object types is reference equality:
let form1 = new System.Windows.Forms.Form()
let form2 = new System.Windows.Forms.Form()
form1 = form1 // true
form1 = form2 // false
However comparison is not permitted:
let form1 = new System.Windows.Forms.Form()
let form2 = new System.Windows.Forms.Form()
form1 <= form2
// Error: The type 'System.Windows.Forms.Form' does not support the 'comparison' constraint.
// For example, it does not support the 'System.IComparable' interface
That’s good! There is no natural ordering for these object - you could define one, on a derived type, by implementing IComparable, but there is not natural ordering provided by the .NET libraries.
Now, unlike other operations in the F# core library, equality and comparison are conditional on the structure of types. For example, you can only use the above equality and comparison operators on a tuple if the constituent parts of the tuple also support equality and comparison. For example, using equality on a tuple of forms is permitted:
let form1 = new System.Windows.Forms.Form()
let form2 = new System.Windows.Forms.Form()
(form1, form2) = (form1, form2) // true
(form1, form2) = (form2, form1) // false
But attempting to order a tuple involving forms is not:
(form1, "Data for Form1") <= (form2, " Data for Form2")
// Error: The type 'System.Windows.Forms.Form' does not support the 'comparison' constraint.
Again, that’s good – this ordering would be a bug in your code.
Many types in the .NET libraries come with custom equality and comparison implementations. For example, System.DateTime has custom implementations of both equality and comparison. F# also allows you to define custom comparison and equality for new type definitions. We’ll be looking at how to customize equality and comparison implementations later in this blog post.
What do the equality and comparison constraints mean?
Let’s summarize where we are so far:
- For some types, equality is structural. Forexample, lists, options, tuples and user-defined structural types.
- For some types, equality is reference based. These types do not tend to support comparison. For example, System.Windows.Forms.Form.
- For some types, equality is customized, for example System.DateTime.
- For some types, there is no sensible notion of equality and/or comparison. You can think of these types as being labelled no equality and no comparison. This case is only important for finding bugs in your code earlier rather than later.
The combination of these points underlies the decision to include equality and comparison constraints as first-class new, primary constraints in the F# language. Later on in this blog post we consider other options in this design space. Now, let’s take a closer look at when equality and comparison constraints are satisfied in F#.
The essence of the rules is very simple:
The constraint type : equality holds if:
- the type definition for type doesn't have the NoEquality attribute,
- any “equality dependencies” of the type also satisfy ty : equality
The constraint type : comparison holds if:
- if the type is a named type, then the type definition doesn't have the NoComparison attribute; and
- the type definition implements System.IComparable; and
- any “comparison dependencies” of the type also satisfy tyi : comparison
These rules mean that an equality constraint is a relatively weak constraint, since nearly all CLI types satisfy this constraint. Reference equality is pervasive in other CLI languages such as C# and this shows through in CLI libraries. Note that the an equality constraint also implies the ability to use the F# hash function on an object.
A comparison constraint is a stronger constraint, since it usually implies that a type must implement System.IComparable.
We’ve discussed the notion of “dependencies” above, e.g. (int * string) is comparable because both int and string are comparable. Here, int and string are dependencies of the tuple type. We’ll look at declaring new dependencies for a type further below.
Defining New Structural Types
Structural type definitions are easy in F#:
type MyBox<'T> = MyBox of 'T
In this case, the type is given structural equality and comparison implementations, and F# infers that there is an equality and comparison dependency on ‘T. All done!
Sometimes you may want to assert that a structural type really MUST support structural equality, and you want an error at the definition of the type if it does not. You do this by adding the StructuralEquality or StructuralComparison attribute to the type
[<StructuralEquality;StructuralComparison>]
type MyIntBox = MyIntBox of int
This simply adds extra checking. In the example below, the code gives an error at compile time, because the type can’t logically support automatic structural comparison, because one of the element types does not support structural comparison:
[<StructuralEquality;StructuralComparison>]
type MyData = MyBox of int * string * string * System.Windows.Forms.Form
More commonly, you may notice that F# function types do not support equality:
[<StructuralEquality;StructuralComparison>]
type MyData = MyBox of int * string * string * (int -> int)
Again this will give an error, because function values are considered to be “no equality”
You can also declare that a structural type should use reference equality.
[<ReferenceEquality>]
type MyFormWrapper = MyFormWrapper of System.Windows.Forms.Form * (int -> int)
In summary, the following attributes control the comparison and equality semantics of types in the cases outlined earlier in this blog post
- StructuralEquality,StructuralComparison – indicates a structural type MUST support equality and comaprison
- ReferenceEquality – indicates a structural type supports only reference equality
- NoComparison, NoEquality – indicates a type doesn’t support equality or comparison at all
- CustomEquality, CustomComparison – indicates a structural type supports custom equality and comparison
Note there is no such thing as “reference comparison” (the object pointers used by .NET move around, so the ordering would change). You might implement that by using a unique tag and custom comparison.
Customizing Equality and Comparison
For some types it is often necessary to define your own comparison, equality and hashing semantics. For example, values of a type may carry a unique integer tag which can be used for this purpose.
In this case our recommendation is to take full control of your destiny and define custom comparison and equality operations on your type. For example, here is how you might compare based on a “stamp” integer value:
/// A type abbreviation indicating we’re using integers for unique stamps on objects
type stamp = int
/// A type containing a function that can’t be compared for equality
[<CustomEquality; CustomComparison>]
type MyThing =
{ Stamp: stamp;
Behaviour: (int -> int) }
override x.Equals(yobj) =
match yobj with
| :? MyThing as y -> (x.Stamp = y.Stamp)
| _ -> false
override x.GetHashCode() = hash x.Stamp
interface System.IComparable with
member x.CompareTo yobj =
match yobj with
| :? MyThing as y -> compare x.Stamp y.Stamp
| _ -> invalidArg "yobj" "cannot compare values of different types"
You might also find these helpful to add to your library of F# helpers:
let equalsOn f x (yobj:obj) =
match yobj with
| :? 'T as y -> (f x = f y)
| _ -> false
let hashOn f x = hash (f x)
let compareOn f x (yobj: obj) =
match yobj with
| :? 'T as y -> compare (f x) (f y)
| _ -> invalidArg "yobj" "cannot compare values of different types"
This can then make your custom implementations more uniform. For example, here is a custom implementation for a union type:
type stamp = int
[<CustomEquality; CustomComparison>]
type MyUnionType =
| MyUnionType of stamp * (int -> int)
static member Stamp (MyUnionType (s,_)) = s
override x.Equals y = equalsOn MyUnionType.Stamp x y
override x.GetHashCode() = hashOn MyUnionType.Stamp x
interface System.IComparable with
member x.CompareTo y = compareOn MyUnionType.Stamp x y
You can also define custom equality and comparison implementations on other types.
Note: A bug in an error message in the 1.9.7 release of F# says “A type with CustomEquality must override Equals or implement IEquatable or IStructuralEquatable”. This is not the case: a type with CustomEquality must override Equals.
Safer Code: Suppressing Equality and Comparison on a Type
You can suppress equality on an F# defined type by using [<NoEquality>] attribute on the definition of the type. This simply means that the type will not be considered to satisfy the equality constraint. Likewise, you can suppress comparison on an F# defined type by using [<NoComparison>] attribute on the definition of the type. This simply means that the type will not be considered to satisfy the comparison constraint.
[<NoEquality; NoComparison>]
type MyProjections =
| MyProjections of (int * string) * (string -> int)
Adding these attributes to your library types makes client code safer, as it is less likely to inadvertently rely on equality and comparison over types where these operations make no sense.
Safer Code: Safer Sets and Maps
All previous versions of F# did not check equality and comparison constraints. We always planned to address this, but the details were only finalized in 1.9.7.
One main motivation for checking these constraints is to make sure the F# Set and Map types, and other future F# immutable collections, are not misused. For example, consider the following:
let x1 = set [ (fun x -> x + 1); id ; (fun x -> x + 2) ] // static error
let x2 = set [ obj(); obj(); obj() ] // static error
let x3 = set [ typeof<int>; typeof<string> ] // static error
In early versions of F# these gave runtime errors. As another example, consider trying to compare functions for equality:
id = id // static error
This returned “false” in early versions of F#, because two different closures were allocated for “id” on each side of the equation – this is valid, according to the F# specification, which says that the results of equality comparison on function values was undefined. This now gives a static error. These cases alone indicate the importance of addressing this issue.
Safer Code: Declaring Conditions for Equality over Container Types
Programmers love defining new generic container types. This is done less often in .NET and F# programming than in other languages, but it's still important!
Equality and comparison play a role here. For example, it is common to have collections where some of the values can be indexed using hashing, or compared for equality when searching, or compared using an ordering. For example, seeing a constraint on this signature on a library type would come as no surprise:
type Graph<'Node when 'Node : equality>() = ...
Indeed the presence of the constraint is somewhat reassuring here, as the requirement on node types is made clearer.
Now, sometimes it is also desirable to be able to compare “entire containers”, e.g. compare one set with another, or one map with another, or one graph with another. This is a lot like comparing tuples or lists. At a first approximation this is done by customizing equality and/or comparison for the container.
type Graph<'Node when 'Node : equality>() =
override x.Equals(yobj) = ...
override x.GetHashCode() = ...
In this case, the node type already supports equality/hashing (for indexing inside the collection ) so the implementation of “Equals” is simple enough, following the pattern laid out in the section “Customizing Equality and Comparison” above.
Sometimes, however, it is necessary to declare that equality (and comparison) over generic container values themselves is “dependent” on the type parameters of the container type. Just like F# list and tuple types. This is done by adding the EqualityConditionalOn and ComparisonConditionalOn attributes to the type parameters of a generic type.
As our example, we will use that beguilingly simple beast – a single-cell container that also supports equality and comparison over the container. You can define this easily in F# as follows:
type MyBox<'T> = MyBox of 'T
In this case, this is a structural type definition, and F# infers that there is an equality and comparison dependency on ‘T. All done! You will be able to use MyBox<_> with values of any type, and you will only be able to do equality and comparison on MyBox values if the element type also supports equality and comparison – perfect!
However, what if MyBox is, for some reason, implemented as a class type, or with customized comparison and equality logic for the type? In this case you need to be more explicit, starting with the EqualityConditionalOn and ComparisonConditionalOn attributes on the type parameter:
type MyBox<[<EqualityConditionalOn; ComparisonConditionalOn >]'T> = ...
With these attributes, MyBox<A> will only satisfy the equality and comparison constraints if A satisfies these constraints. You will still be able to use MyBox<_> with any type.
Now, let’s look at the custom implementations for Equals, GetHashCode and System.IComparable. Here’s a full example of a container type that also supports conditional equality and comparison over the containers themselves:
type MyBox<[<EqualityConditionalOn; ComparisonConditionalOn >]'T>(value : 'T) =
member x.Value = value
override x.Equals(yobj) =
match yobj with
| :? MyBox<'T> as y -> Unchecked.equals x.Value y.Value
| _ -> false
override x.GetHashCode() = Unchecked.hash x.Value
interface System.IComparable with
member x.CompareTo yobj =
match yobj with
| :? MyBox<'T> as y -> Unchecked.compare x.Value y.Value
| _ -> invalidArg "yobj" "cannot compare values of different types"
Note that the implementation of the interfaces and overrides uses “unchecked equality and comparison”, something we’ll get to below. The need for unchecked equality here ultimately stems from the dual facts that
(a) F# asks you to specify custom equality at the level of .NET overrides and interface implementations; and
(b) .NET does not support conditional interface and override implementations (see discussion below).
There are great advantages to (a) – it simplifies F# and means you don’t have to look up the F# manual to see what behaviour your objects will have when handed over to C#.
Fortunately, the use of unchecked equality is isolated and localized, and actually surprisingly hard to get wrong. In any case, you should unit test to check that your type really does support equality and comparison correctly.
Getting IEqualityComparer<’T> and IComparer<’T> Implementations which use F# Generic Equality
When using .NET libraries, it is very common to need an implementation of IEqualityComparer<'T> or IComparer<'T>. Two F# core library functions are very useful for getting objects which implement these interfaces in a way that is consistent with F# equality and comparison:
HashIdentity.Structural<'T> : IEqualityComparer<'T> when 'T : equality
ComparisonIdentity.Structural<'T> : IComparer<'T> when 'T : comparable
These are most useful when instantiating .NET hash table and comparison operations. For example:
open System.Collections.Generic
let hashTable = new Dictionary<string,int>(HashIdentity.Structural<string>)
let hashSet = new HashSet<string>(HashIdentity.Structural<string>)
You can also omit some of the type annotations here and let inference do its work:
open System.Collections.Generic
let hashTable = Dictionary(HashIdentity.Structural)
let hashSet = HashSet(HashIdentity.Structural)
hashTable.Add("three", 3)
hashSet.Add("three")
The great advantage of giving an explicit HashIdentity.* or ComparisonIdentity.* argument is that your code is more rigidly checked: the F# compiler checks if your inferred key type actually admits F# equality. For example, F# function types are considered to be “no equality” (i.e. hashing on an F# function values is not a good idea):
open System.Collections.Generic
let concatOne (s:string) = s + "1"
let hashTable = new Dictionary<_,_>(HashIdentity.Structural)
hashTable.Add(concatOne, 10) // error: the type “string -> string” doesn’t support equality
Here the intended code was something like this:
hashTable.Add(concatOne "ten", 10) // ok: the type “string” supports equality
Using unchecked equality and comparison
As we saw above, it can occasionally it can be necessary to resort to “unchecked” equality and comparison on values. This doesn’t do any static checking, just like in earlier versions of F#.
Unchecked.equals: 'T -> 'T -> bool
Unchecked.hash: 'T -> int
Unchecked.compare: 'T -> 'T -> int
These are unconstrained operations, and work just the same way as the constrained operations – for example, they will also by optimized by the F# compiler if used on basic integer types. For Unchecked.equals and Unchecked.hash, they are semantically similar to converting to the type “obj” and doing equality over that static type.
Design Alternatives. Could interface constraints suffice? What about type classes?
Readers familiar with C# may ask “Does F# really need a new kind of constraint here? How about using an interface constraint?”. For example, could we use this signature for comparison?
compare : 'T -> 'T -> bool when 'T : System.IComparable
Or this one?
compare : 'T -> 'T -> bool when 'T : System.IComparable<'T>
The problem with both is that they are too permissive: for example, if F# lists implement IComparable or IComparable<'T>, then the above signatures would let you use comparison on any two F# lists, regardless of whether the element type supports comparison.
The underlying (and well known) problem is that interface implementation in .NET is unconditional – a type either supports an interface or it doesn’t. This is a fundamental limitation of .NET generics. In F#, it is part of our design methodology to add additional, erased constraints to work around such limitations.
Equally it is also not possible to use a parameter constraint on the F# list type. For example, consider this option:
type FSharpList<'T when 'T : IComparable<'T>>() = ... // this leads the type to be over-constrained.
With this signature, lists become much less useful: you couldn’t create lists of objects that don’t support comparison!
As a result, .NET interface constraints are not sufficient to allow us to tackle equality and comparison constraints in F#. This underlies the decision to include equality and comparison constraints as new, erased constraints in the F# language.
Readers familiar with Haskell and other functional languages will be well informed of all the issues relating to equality and comparison, since the issues are fundamental to equality and comparison in any typed language, but particularly functional languages. The mechanisms used to address these points in F# are reminiscent of a weak form of type classes, particularly in the way equality and comparison are dependent on the structure of types, and the way these dependencies can be declared for any type. Haskell also lets users define their own constraints, in a very rich (and sometimes fairly complicated!) way.
Now, equality and comparison are the only operations in the F# Core Library that are statically conditional on the structure of types. This raises the question as to why F# doesn’t allow user-defined constraints (beyond interface constraints), and why other constraints can’t be declared conditional. After all, it is well known that it can be useful to make other operations conditional on structure too, e.g. printing and serialization.
The answer is two-fold. Firstly, in future versions of F# we may consider extending the mechanisms used to implement equality and comparison constraints to include user-defined constraints.
Secondly, however, for many common used constraints (such as formatting and serializability), there are other ways to achieve the same thing in F# that are not particularly amenable to using constraints. Also, in each case there are serious interactions with .NET libraries and existing design practice to consider. Finally, some conditional constraints would require a “dictionary passing” implementation. This brings added difficulties. Equality and comparison constraints are not dictionary passing – they are ultimately implemented via interfaces and overrides. As a result, for F# in Visual Studio 2010, we concentrated on resolving the interactions with .NET for the critical cases of equality and comparison, rather than adding a completely general mechanism.
Summary
F# equality and comparison constraints tighten up a key part of the F# language, they make user code safer and simpler.
On the whole, F# code is surprisingly unaffected by these constraints – in our test trees we have a very large collection of sample F# code, and only a very small amount of that code needed to have equality or comparison constraints added. These constraints catch problems, but do not intrude. For example, we use structural and equality constraints throughout the F# compiler codebase and, in a couple of cases, it helped to identify lingering potential bugs.
In 1.9.7 we also simplified some of the attributes used to control equality and comparison, notably removing the “true” and “false” arguments from StructuralEquality etc., and adding CustomEquality to help users declare exactly what is intended. If you need additional help to adjust your code for these changes, please let us know.
We wish you many happy days of safer and more productive coding!
Comments
Anonymous
November 09, 2009
> The constraint type : comparison holds if ... the type definition implements System.IComparable So IComparable<T> is not accepted?Anonymous
November 25, 2009
Hello Don Syme ! Im am a beginer programmer . So, i am strying comparation F# and Ocaml to find the better language to study , but i don't know how to comparation they , because i see there are alot of comparation F# and Ocaml in the Web and the Blog , but it is not details, it don't talk what is the most difference of F# and Ocaml. Would you like tell me about what differences of F# and Ocaml. Thank so much !