F# Math (III.) - Defining custom numeric types

In this article, we define an F# numeric type for calculating in the modular arithmetic (also called clock arithmetic) [1]. Modular arithmetic is used for calculations where we want to keep a value within a specified range by counting in cycles. For example, a maximal value on clock is 12 hours. When we add 11 hours and 3 hours, the value overflows and the result is 2 hours. Aside from clocks, this numeric system is also essential in cryptography or, for example, in music.

This tutorial shows several techniques that are essential when defining any new numeric type in F#. Most importantly, you’ll learn how to:

• Define a numeric type with overloaded operators
• Define a numeric literal for constructing numbers of our new type
• Enable calculating with our type in F# lists and matrices
• Hide implementation details of a numeric type

We define type IntegerZ5 that implements modular arithmetic with modulus 5, meaning that valid values are in the range from 0 to 4 and we equip the type with operations such as addition and multiplication. When an operation produces a value that would be outside of the range, we adjust it by adding or subtracting the modulus (in our case 5). Here are some examples of calculations that we’ll be able to write:

2 + 1 = 3 (mod 5)
4 * 2 = 3 (mod 5)
List.sum [ 0; 1; 2; 3 ] = 1 (mod 5)

In the first case, we can perform the operation without any adjustments. In the second case, we multiply 4 by 2 and get 8 as the result, which is out of the required range. To correct it, we calculate the remainder after a division by 5 (written as 8 % 5 in F#), which gives us 3. Finally, the last example shows that we’d also like to be able to use our type with lists. If we add values 0, 1, 2 and 3, we get 6 which is adjusted to 1.

This article is a part of a series that covers some F# and F# PowerPack features for numerical computing. Other articles in this series discuss matrices, defining custom numeric types and writing generic code. For links to other parts, see F# Math - Overview of F# PowerPack.

Defining the IntegerZ5 type

We’ll create an F# library containing our numeric type, so that it can be easily used from multiple applications. The approach we’ll use will follow the usual F# best practices for designing this kind of libraries, so you should follow similar steps when creating any other numeric type.

To start, we create a new F# Library project in Visual Studio. Once the project is created, remove the existing files and add a new file named IntegerZ5.fs. This file will contain the implementation of our type. We start by adding a type IntegerZ5 into a namespace FSharp.Numeric:

 1: namespace FSharp.Numerics
 2: 
 3: type IntegerZ5 = 
 4:   | Z5 of int
 5:   member z.ToInt32() =  
 6:     let (Z5 n) = z in n
 7:   override z.ToString() = 
 8:     sprintf "%d (mod 5)" (z.ToInt32())
 9: 
10:   static member Create(n) = 
11:     let z5 = n % 5
12:     Z5(max ((z5 + 5) % 5) z5)

The type is implemented as a discriminated union with a single case labeled Z5. The case carries a value of type int, but the operations that we’ll provide for creating and calculating with IntegerZ5 will guarantee that the actual value will be within the required range (0 to 4, inclusively). The fact that we use single-case discriminated union is merely an implementation detail that allows us to implement operations with the type in a convenient way, but we'll later see how to hide this implementation detail.

The first two members convert an IntegerZ5 value to other types. To get an integer, we simply return the underlying value. When formatting the value as a string, we append the "(mod 5)" string after the number, which is the usual way of denoting that the number is in the modular arithmetic.

The last static members provide ways for constructing IntegerZ5 values. It takes an arbitrary integer as an argument and adjusts it, so that it is within the specified range. This is done by calculating the remainder of a division by 5 and adding 5 in case the result is negative (for example, -13 % 5 produces -3, and the result of max -3 2 will give us 2).

So far, we created a simple type that can be created and printed, but that’s all we can do with it so far. In the next section, we’ll equip our type with basic operators for calculating with it. As we’ll see, that’s all we need to use the type with some standard F# library functions.

Creating and calculating with IntegerZ5

Next, let's take the IntegerZ5 type and add operators for multiplying, adding and subtracting values of this type. We’ll also add two members that provide easy access to frequently used constants 0 and 1 and we’ll provide a simple function for constructing values of this type. The following listing adds several static members to the type:

1: type IntegerZ5 = 
2:   (Omitted)
3:   static member (+) (Z5 a, Z5 b) = IntegerZ5.Create(a + b)
4:   static member (-) (Z5 a, Z5 b) = IntegerZ5.Create(a - b)
5:   static member (*) (Z5 a, Z5 b) = IntegerZ5.Create(a * b)
6:   static member Zero = Z5 0
7:   static member One  = Z5 1

The three overloaded operators are implemented as static members with a special name. They take two parameters of type IntegerZ5 and we use pattern matching (using the discriminated union case label Z5) to immediately extract the actual integer used to represent the number. After performing the numerical operation on integers, the result may be out of the specified range, so we construct the result using the Create member, which adjusts the integer. The Zero and One members simply construct value using the Z5 union case, because 0 and 1 are always valid values (so there is no need for calling the Create member).

Most of the standard F# numeric types can be created from other numeric types by calling a conversion function of the same name as the name of the type. For example float 42 returns a floating point number 42.0 and byte 42.0 converts a floating point number to a byte value 42uy.

Numeric type conversion functions are written in a way so that they work with any numeric type that supports the conversion in some way. This means that we can write byte 42 as well as byte 42.0, but not for example byte (new System.Random()). This behavior is achieved using static member constraints, which allow the function to specify that the argument needs to be of any type that provides a specific method.

To write a conversion function for IntegerZ5 type, we could either use static member constraints explicitly, or we can use some existing function (such as int) and let the F# type inference deduce the constraints automatically. The following listing uses the second approach:

1: [<AutoOpen>]
2: module IntegerZ5TopLevelOperations = 
3:   let inline z5 a = IntegerZ5.Create(int a)

The function z5 needs to be marked as inline, which allows us to use static member constraints. Inside the body, we first convert the argument to an integer using the int function and then construct IntegerZ5 from the returned integer. The static member constraints are propagated automatically and we’ll look at them in more details later.

Since functions cannot be declared inside a namespace, we need to enclose our function in a module. We want to make it available automatically whenever the user of our library opens the FSharp.Numerics namespace, which can be done by adding the AutoOpen attribute to the module declaration.

Testing numeric type interactively

As a next step, we’ll use F# interactive to verify that the code we wrote so far works as expected. At this point, we didn't even build the library. We just wrote some F# source code and want to test the source code without building the library. We'll use interactive tests written in an F# script file. Once you build the library, it is quite easy to turn those into proper unit tests using NUnit, xUnit or other testing frameworks.

To test the type we implemented at the source code level, we first add a new F# Script File (Add -> New Item... -> F# Script File) named Tests.fsx. In this file, we load the content of IntegerZ5.fs and register a printer to specify how the F# Interactive tool should output values of our type:

1: #load "IntegerZ5.fs"
2: open FSharp.Numerics
3: 
4: fsi.AddPrinter(fun (z:IntegerZ5) -> z.ToString())

The first command loads an F# source code and evaluates it in the F# Interactive tool. Next, we open the namespace FSharp.Numerics, which contains our type. Finally, we call the AddPrinter member of the global fsi value. The parameter is a lambda function that takes value of our IntegerZ5 type and returns a string by simply calling the ToString member we provided. Note that we need to add the type annotation, because AddPrinter is a generic member. The type annotation allows it to determine a type for which we’re specifying the printer.

Now, we can test our function for creating IntegerZ5 values and operators for working with them:

1: let a = z5 3.0
2: let b = z5 7
3: val a : IntegerZ5 = "3 (mod 5)"
4: val b : IntegerZ5 = "2 (mod 5)"
5: 
6: a * b;
7: val it : IntegerZ5 = "1 (mod 5)"
8: a + b
9: val it : IntegerZ5 = "0 (mod 5)"

As we can see, when the F# Interactive outputs a value of our type, it uses the printer we specified. The output such as “3 (mod 5)” makes it clear that the value is calculated in modulus arithmetic of base 5. The first two let bindings show that the z5 function works with any numeric types (including floating point numbers and integers) and that it automatically calculates the modulus of the number. The last two examples show that overloaded operators we provided also follow the rules of modulus arithmetic.

So far, we’ve been using the operators directly. The way we wrote the IntegerZ5 type also allows us to use it with some functions from the F# core libraries. For example, if we create a list of IntegerZ5 values, we can sum the list using the overloaded operators we provided simply like this:

1: List.sum [ z5 0; z5 1; z5 2; z5 3; z5 4 ]
2: val it : IntegerZ5 = "0 (mod 5)"

How does the List.sum function know that it needs to use the overloaded operator of IntegerZ5 type? The function is implemented using static member constraints and requires that the type of the elements provides a + operator and also a Zero member. The compiler knows that our type provides the required members, so it allows us to use List.sum for our type. We'll look at implementing functions like this in the next article of the series.

When creating values of IntegerZ5 in this step, we used the z5 conversion function. Alternatively, we could use the IntegerZ5.Create member, but that leads to a more heavyweight notation. In the next step, we’ll see how to use numeric literals to make the syntax more convenient.

Providing numeric literals for IntegerZ5

Values of built-in numeric types such as int64, byte or float32 can be created using special numeric literals -30L, 127uy and 42.0f. The F# makes it possible to provide a similar literal for our own numeric types. There are several limitations to what kind of literals we can define. Briefly, the literal must end with one of characters that are reserved for this purpose by the F# language. Additionally, the literal must consist only of numeric symbols (so for example 12#3Z isn’t allowed).

To define a literal, we need to write a module with a special name. Inside the module, we implement several functions that are used automatically in the F# compiler whenever a literal is used:

1: module NumericLiteralZ = 
2:   let FromZero () = Z5 0
3:   let FromOne  () = Z5 1 
4:   let FromInt32 a = IntegerZ5.Create(a%5)
5:   let FromInt64 a = IntegerZ5.Create(int(a%5L))

The name of the module consists of the special name NumericLiteral followed by a symbol Z which we’ll use for writing our literals. This means that we’ll be able to write literals such as 0Z, 1Z and 42Z. The module may provide several functions to enable several sizes of literals.

If we included only the first two functions (FromZero and FromOne) we would be able to write only 0Z and 1Z. The next two functions enable writing literals for other numbers that fit into integer values. To support numeric literals that are larger than int64, we could also provide the FromString method. Note that this wouldn’t allow writing literals consisting of non-numeric characters. The main use of this method is to enable arbitrarily sized integer values, so we don’t provide it in the above example.

The following listing shows a few examples of using our newly defined numeric literals:

1: 6Z
2: val it : IntegerZ5 = "1 (mod 5)"
3: 3Z * (4Z + 2Z)
4: val it : IntegerZ5 = "3 (mod 5)"

As we can see, numeric literals make working with custom numeric data types easier. Since our numeric type is almost finished now, we’ll look at compiling it into a redistributable library in the next step.

Adding F# Signature file

Signature files can be added to a project to specify which of the members and values from an implementation file (such as IntegerZ5.fs) should be publicly exported by the compiled library. A signature file lists members and functions together with their type signatures, which also makes it a useful source of information about our library.

The name of the file should be the same as the name of the implementation file, but it should have the fsi extension. In our case, we’ll add a file named IntegerZ5.fsi. The file needs to be passed to the compiler before the implementation file. In Visual Studio, this means that you need to move the file before the implementation file in the Solution Explorer. This can be done by right-clicking on the file and selecting the “Move Up” command.

The listing below shows the source code of the signature file. Most of the type signatures that you can see in the listing can be inferred automatically by the F# compiler. An easy way of extracting the first version of F# signature file from the source code is selecting the entire content of the implementation file and evaluating it interactively. The F# Interactive prints all the inferred type signatures and we can easily copy them to the signature file.

Nevertheless, we’ll need to make one notable addition to the generated type signature. The listing also shows the type signature of the z5 function, which is quite interesting:

 1: namespace FSharp.Numerics
 2: 
 3: [<Sealed>]
 4: type IntegerZ5 =
 5:   member ToInt32 : unit -> int
 6:   override ToString : unit -> string
 7:   static member Create : int -> IntegerZ5
 8:   static member One : IntegerZ5
 9:   static member Zero : IntegerZ5
10:   static member ( + ) : IntegerZ5 * IntegerZ5 -> IntegerZ5
11:   static member ( * ) : IntegerZ5 * IntegerZ5 -> IntegerZ5
12:   static member ( - ) : IntegerZ5 * IntegerZ5 -> IntegerZ5
13: 
14: module NumericLiteralZ = 
15:   val FromZero  : unit -> IntegerZ5
16:   val FromOne   : unit -> IntegerZ5
17:   val FromInt32 : int -> IntegerZ5
18:   val FromInt64 : int64 -> IntegerZ5
19: 
20: module IntegerZ5TopLevelOperations = 
21:   val inline z5 : ^a -> IntegerZ5 when  
22:         ^a : (static member op_Explicit :  ^a -> int)

The signature file starts with a namespace declaration, which is the same as the declaration in the implementation file. Next, it contains a single type signature and two module signatures. Note that the IntegerZ5 type is marked with the Sealed attribute. This is required, because the signature file needs to reveal what kind of file we are declaring. For F# types such as records and discriminated unions, we use Sealed meaning that the type is not extensible.

Type signatures of the members of our numeric type as well as functions in the NumericLiteralZ module are mostly straightforward. The function z5 in the last module is far more interesting. As noted earlier, the function is implemented so that it works on any argument that can be converted into an integer. In practice, this means that the type of the argument needs to provide a static member named op_Explicit taking the type of the argument and returning integer.

Determining whether a type of the argument has a certain method cannot be expressed in .NET generics, so we use F# specific feature named static member constraints. This works only for so-called hat types (such as ^a). Hat types are inlined during the compilation, so the function also needs to be marked as inline.

Finally, it is also worth noting that if we added op_Explicit member to our IntegerZ5 type, it would be possible to use our type as parameter of the int function (so we could write for example int 3Z).

Supporting matrices using global associations

Our numeric type can be used with some standard library functions such as List.sum, because they implement certain members that are required by static member constraints of List.sum. However, this approach doesn't work with complex data types such as generic matrices. If we try to write any matrix computation with our type, it will not work, because generic Matrix type isn’t automatically able to use the overloaded operators and members we provided.

In order to support matrices we need to provide a so-called numeric association. This is a simple interface containing numeric operations that can be performed on our type. The interface needs to be registered in a global table maintained by the F# PowerPack library, so that any F# code can get the interface from the table and use it for performing operations with our type.

The F# PowerPack library contains a hierarchy of interfaces that represent various sets of numeric operations that we may be able to provide. We’ll implement the most basic interface called INumeric<'T> and represent a simple numeric type. Other interfaces available are for example IIntegral<'T>, which provides operations such as DivRem (division with a remainder) or IFloating<'T>, which additionally includes floating point operations such as Sqrt.

The simplest way to implement the interface is to use object expressions and create a singleton value implementing it. We also need to provide an operation that registers the instance in the GlobalAssociations table:

 1: module IntegerZ5Associations = 
 2:   let IntegerZ5Numerics = 
 3:     { new INumeric<IntegerZ5> with 
 4:          member z.Zero = IntegerZ5.Zero
 5:          member z.One = IntegerZ5.One
 6:          member z.Add(a,b) = a + b
 7:          member z.Subtract(a,b) = a - b
 8:          member z.Multiply(a,b) = a * b
 9:          member z.Equals(Z5 a, Z5 b) = (a = b)
10:          member z.Compare(Z5 a, Z5 b) = compare a b
11:          member z.Negate(a) = 0Z - a
12:          member z.Abs(a) = a
13:          member z.Sign(Z5 a) = Math.Sign(a)
14:          member z.ToString(Z5 n,fmt,fmtprovider) = 
15:            n.ToString(fmt,fmtprovider) + " (mod 5)"
16:          member z.Parse(s,numstyle,fmtprovider) = 
17:            z5 (System.Int32.Parse(s,numstyle,fmtprovider)) }
18: 
19:   let Init() = 
20:     GlobalAssociations.RegisterNumericAssociation IntegerZ5Numerics

Most of the operations can be implemented directly in terms of operators that we already provided in the IntegerZ5 type, so the purpose of the INumeric<'T> interface is simply to make these operations accessible indirectly. Some other operations such as Compare, Sign or ToString can be implemented using the underlying integer (which we can extract by writing the pattern Z5 a in place of parameter).

The module also provides Init function, which registers our instance in the GlobalAssociations table. Ideally, the registration would be done automatically when the IntegerZ5 type is used for the first time, but this is unfortunately not easy to achieve. Instead, we'll write a function that needs to be called explicitly (to make this automatic, you could move the code to a static constructor of the IntegerZ5 type).

To make the module visible in the compiled library, we also need to include its type signature in the F# Signature file that we added earlier. This can be done by adding the code from the following listing:

1: module IntegerZ5Associations = 
2:   val IntegerZ5Numerics : INumeric<IntegerZ5>
3:   val Init : unit -> unit

Now that our library is complete, we can compile and use the created assembly in other F# projects. In this tutorial, we didn’t aim to create a C# compatible type, however, the type would be also usable from C# (most importantly, all the overloaded operators and members of the type would work in C#).

As a final step, we’ll look how to load the compiled library in F# interactive and use our type to do a simple computation using generic Matrix type:

 1: #r "FSharp.PowerPack.dll"
 2: #r "bin\Debug\FSharp.Numerics.dll"
 3: 
 4: open FSharp.Numerics
 5: module MatrixG = Matrix.Generic
 6: 
 7: IntegerZ5Associations.Init()
 8: 
 9: let ys = MatrixG.init 5 5 (fun a b -> (z5 a))
10: let xs = MatrixG.init 5 5 (fun a b -> (z5 b))
11: val ys : Matrix<IntegerZ5> = (...)
12: val xs : Matrix<IntegerZ5> = (...)
13: 
14: xs .* ys
15: val it : Matrix<IntegerZ5> =
16:   matrix [[0 (mod 5); 0 (mod 5); 0 (mod 5); 0 (mod 5); 0 (mod 5)]
17:           [0 (mod 5); 1 (mod 5); 2 (mod 5); 3 (mod 5); 4 (mod 5)]
18:           [0 (mod 5); 2 (mod 5); 4 (mod 5); 1 (mod 5); 3 (mod 5)]
19:           [0 (mod 5); 3 (mod 5); 1 (mod 5); 4 (mod 5); 2 (mod 5)]
20:           [0 (mod 5); 4 (mod 5); 3 (mod 5); 2 (mod 5); 1 (mod 5)]]

After referencing F# PowerPack and our library, we open the namespace FSharp.Numerics, which contains our type and define a module alias MatrixG to simplify access to generic Matrix type. Next we call the Init function to register the global numeric associations for our type.

Finally, we construct two matrices of the size 5x5 – the first one contains increasing values of the IntegerZ5 type along the first dimension and the values in the second matrix increase along the second dimension. We use point-wise multiplication of these two matrices to produce a simple table that shows results of multiplying all possible combinations of IntegerZ5 values.

Summary

In this article, we looked at implementing a custom numeric type. Although you probably won't need to implement a custom numeric type very often, it may be useful. Aside from modular arithmetic, you may want to implement a type that represents quadruples of values (to represent colors) or a type to represent 3D vectors. The F# PowerPack library uses the techniques described in this article to implement BigRational and complex types that I introduced in an earlier article.

When implementing a numeric type, there is quite a few features that you may want to support. In this article, we defined overloaded operators and members that are required by static member constraints, so that we could use functions like List.sum. Then we also defined numeric literals to be able to write 1Z instead of z5 1. Finally, we implemented the INumeric<'T> interface, which makes it possible to use our type with generic matrices from F# PowerPack, which I covered in the previous article of the series.

References & Links

• [1] Modular arithmetic - Wikipedia.org
• [2] F# PowerPack (source code and binary packages) - CodePlex
• [3] Numeric Computing - Real World Functional Programming on MSDN
• [4] Numerical Libraries for F# and .NET - Real World Functional Programming on MSDN