Marcelo Zabani's coding blog

Interfaces and typeclasses: Number APIs in C# and Haskell

Advertisements

In C# sometimes I sorely miss something like an INumber<T> interface with methods Add, Subtract, Multiply and others. The lack of this means it is cumbersome to write generic code on numbers. It means that instead of writing something like:

T Sum(IEnumerable<T> numbers) where T : INumber<T>;

We have to write all possible overloads:

double Sum(IEnumerable<double> numbers);
float Sum(IEnumerable<float> numbers);
decimal Sum(IEnumerable<decimal> numbers);

The implementation body of all these functions will be exactly the same, but we have to write it multiple times anyway. Some people work this out by creating generic methods for the operations they need while resorting to runtime type-checking:

T Add(T a, T b) {
  if (a is double) {
    return (double)a + (double)b;
  }
  else if (a is int) {
    return (int)a + (int)b;
  }
  // .. and so on
}

This is not a terribly good solution, however, since we have no compile-time guarantees that the type T is a number at all, not to mention the performance costs of runtime type-checking. What’s more, this solution can’t be extended to new types; what if someone writes a Complex class to represent complex numbers? The implementation of Add would have to be open for modification, so this code could never be packaged in a library.

Sadly, it is hard to solve this conundrum without changing the Base Class Libraries themselves. The only thing we could hope for is for the people at Microsoft to design numeric interfaces such as INumber<T> (or others) and make our well-known primitive numeric types implement these interfaces.

Enter Haskell.

Haskell is the programming language I’ve been playing with for the last year, and except for the steep learning curve, I have only good things to say. It can be extremely expressive and it is amusing to see that when my code builds it almost certainly works! It is also extremely terse, as you can easily see by this window manager’s less than 2000 lines of code, xmonad, and by the code on this post.

In Haskell, the problem shown above can be solved with typeclasses, which we can think of for now as something similar to interfaces, since they specify a contract that concrete types must obey. The big difference here is that when we create a typeclass, we can make types we don’t own implement (in Haskell: instantiate) it! This means we can design our numeric typeclasses and have Haskell’s standard numeric types, such as Data.Int and Data.Complex, instantiate them! What’s more: in Haskell we can create functions named “+”, “*”, “/”, “-” with infix application. No need to differentiate operators from regular functions: they are one and the same!

module Numeric where -- "Numeric" will be the namespace in which the definitions below will live

import qualified Prelude -- The prelude is a base set of types, typeclasses and functions that are used for common tasks

-- The "class" construct actually creates a typeclass (similar to an interface). Here we say that concrete types that instantiate this typeclass must implement functions called "+" and "*", both of them receiving two parameters of type "t" and returning an object of type "t" as well
class Number t where
  (+) :: t -> t -> t
  (*) :: t -> t -> t
  zero :: t

-- Specifies the type "Int", which we don't own, as an instance of "Number". The Add and Multiply functions already exist in Haskell inside the Prelude. We'll use those.
instance Number Prelude.Int where
  a + b = (Prelude.+) a b
  a * b = (Prelude.*) a b
  zero = 0

-- Now we can define a generic "sum" function with sums all numbers in a list. The following line says that type "t" must be an instance of the typeclass "Number", and that it receives a list of t and returns t. There are better ways to write this in Haskell, but that is not important right now
sum :: Number t => [t] -> t
sum [] = zero -- This is our base case: empty list sums to zero
sum (x:xs) = x + sum xs -- This separates the first element in the list, "x", from the remaining list, "xs"

Note to the reader: Haskell’s prelude already comes with a Num typeclass with more than just addition and multiplication, and existing numeric types already implement those.

And that’s it! The syntax up there really is that short, and it really is type-checked! Also, it only scratches the surface of Haskell is capable of. Believe me, just a tiny scratch.

It is important to notice here that in C# it is entirely possible to make new types that can be added to existing types by defining a public static T operator +(T a, T2 b) in the new type T. What we can’t do is specify generic type constraints that allow us to work with numeric types. In reality, this is not just about numeric APIs: it is just a consequence of the fact that we can’t make types we don’t own implement interfaces, combined to the fact that parametric polymorphism only allows restrictions based on subclassing or interface implementation (with the exception of the new(), struct and class constraints).

It is not hard to think of how useful typeclasses can be. Why doesn’t IList and ICollection implement IReadOnlyCollection anyways? Maybe we want both StringBuilder and System.String to implement IString, allowing for generic code that doesn’t need to convert between one and another. There are many possibilities out there.

Let’s take this a little further, because  it can get pretty interesting: how about subtraction? In C# we can subtract a TimeSpan from a DateTime and get another DateTime. Subtracting an int from an int, however, yields another int. Can we encode this information in Haskell in a way that is checked by the compiler itself, allowing us to write generic code that is able to subtract one object from another? The answer is yes.

More: can we develop a set of typeclasses that makes sure that arithmetic operations will NEVER overflow? This would really help us write banking software, for example, allowing us to add and subtract enormous values without worrying about it. With two language extensions called MultiParamTypeClasses and TypeFamilies we can!

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TypeFamilies #-}
module Numeric where

import qualified Prelude
import Prelude (Int, Integer, toInteger, negate) -- These types and functions will be available without the need to be prefixed by "Prelude."
import Data.Time

class Subtractive t1 t2 where
  type Difference t1 t2 :: * -- This is just a fancy way of saying that the combination of "Difference" and two types is meant to represent another type
  (-) :: t1 -> t2 -> Difference t1 t2

-- In Haskell the type "Integer" represents arbitrarily large integers. They are like "BigInteger" in .NET or Java. Our implementation of (-) is exactly the same as Prelude's in this case.
instance Subtractive Integer Integer where
  type Difference Integer Integer = Integer
  (-) = (Prelude.-)

instance Subtractive Int Int where
  type Difference Int Int = Integer;-- Here we say that the Difference between two Ints is an Integer, because no matter how small two Ints are, their difference is always representable as an Integer
  a - b = (toInteger a) - (toInteger b)

-- Let's just enjoy ourselves a little and put in some date and time types in the mix
instance Subtractive UTCTime NominalDiffTime where
  type Difference UTCTime NominalDiffTime = UTCTime
  a - b = addUTCTime (negate b) a

-- The function below works for any two types t1 and t2 which allow for (t1 - t2). It takes in a list of tuples and returns a list of the differences between the two elements in each tuple.
someGenericDifferenceFunction :: Subtractive t1 t2 => [(t1, t2)] -> [Difference t1 t2]
someGenericDifferenceFunction [] = []
someGenericDifferenceFunction ((a, b) : xs) = (a - b) : someGenericDifferenceFunction xs -- Quick reminder: ":" is a function that takes an element and a list and prepends the element into the list

The example above is still incomplete: we need instances of Subtractive Integer Int and Subtractive Int Integer for this API to become more practical. This is left to the reader, however. Meanwhile, let’s try this out in ghci:


terminal> ghci
ghci> :l Numeric.hs
*Numeric> let list = [(1, 2), (5, 5), (10, 3)] :: [(Int, Int)] -- We need to specify the type of "list" because literals could be any type that implements "Num", including Int and Integer.
*Numeric> let difs = someGenericDifferenceFunction list
*Numeric> difs
[-1,0,7]
*Numeric> :t difs
difs :: [Integer]

C# is great and a lot of what we achieved with Haskell could be achieved through an ISubtractive<T, T2, TResult>, if only we could make existing types implement it. We could also create structs that simply wrap existing types and write implicit coercion rules from (and to) them, making these new types implement our custom interfaces, and make a lot of things possible with that, but we wouldn’t be able to pass an instance of IEnumerable<WrapperType> as a replacement for a IEnumerable<WrappedType> without explicit casting, for example, and we’d also have to watch out and stay away from built-in arithmetic operators, since they might no longer obey the relations between types specified through the interfaces (we might want int + int = BigInteger).

So that’s it. I hope you’ve enjoyed your reading, but most of all I hope any C# or Java (or any other mainstream language) developer that reads this gives Haskell a shot. It really is an amazing language.

Any comments and corrections are very welcome!

Advertisements

Advertisements