The F# overload-o-phone

March 20th, 2009

By now, you’ve probably heard the standard line.  Functional programming is all sweetness and light; if we merely cast off the detritus of bad habits we’ve learned from C, C++ and Java we’ll find ourselves in a different world, a better world.  Without state, and by dint of a civilized logical system of analysis, all wishes will come true.

Yet, in the world of F# (and OCaml in a slightly different case), we encounter some logical anomalies:

> (+);;
val it : (int -> int -> int)
> 3.2 + 5.4;;
val it : float = 8.6

Which is the truth here?  Initially we’re told that the “+” operator expects two int values, but it seems to happily accept two floats.  Worse yet, if we expect to rely on this magical addition, our hopes are soon dashed:

> let twice x = x + x;;
> twice 9.4;;
  ——^^^
stdin(2,5): error FS0001: This expression has type
    float
but is here used with type
    int.

Our only chance for generic arithmetic (over ints, floats, vectors, etc) is to explicitly pass the necessary arithmetic functions around:

> let twice fn x = fn x x;;
val twice : (‘a -> ‘a -> ‘b) -> ‘a -> ‘b

> twice (+) 1;;
val it : int = 2
> twice (+) 1.2;;
val it : float = 2.4
> twice (fun (a,b) (c,d) -> (a+c,b+d)) (1,2.3);;
val it : int * float = (2, 4.6)

And although this works, it has a kind of Jerry Seinfeld “why don’t you just tell me the function you want to call?” feel to it.  There must be a better way.

Implicit, Ad-Hoc Polymorphism

This problem is all the more frustrating, because we can resolve it so easily in C++:

int    twice(int    x) { return x+x; }
double twice(double x) { return x+x; }

20 years ago, Phil Wadler and Stephen Blott developed an effective solution to this problem, in How to make ad-hoc polymorphism less ad hoc.  The result has been arguably one of the most significant advances made by the programming language Haskell.  It’s a tool that could be put to good use if it was included in F#.

In investigating this aspect of Haskell, it’s instructive to open a GHC prompt and ask for the “+” operator’s type:

Prelude> :t (+)
(+) :: (Num a) => a -> a -> a

This type signature tells us that the “+” operator will, for any type ‘a’, take two ‘a’ values as input and produce an ‘a’ value as output, provided that ‘a’ represents a “number.”  Likewise, if we use it in our own functions:

Prelude> let twice x = x + x
Prelude> :t twice
twice :: (Num a) => a -> a

We find that the same kind of type signature persists, and that we can safely use it on any number:

Prelude> twice 1
2
Prelude> twice 3.4
6.8

What’s going on here?  Essentially, our code is still translated to something like the moviephone-esque F# example above, except that the compiler decides which actual arithmetic functions to use at the last possible moment (when the type ‘a’ above is decided, however distant that is from the innermost function’s use of the “+” operator) by a kind of “moviephone-transform” of your program (more detail on this transform in a future post).  This added constraint “Num a =>” says that ‘a’ belongs to the “Num” type-class, and this type-class membership is defined by the programmer on an ad-hoc basis.

For example, suppose that we’ve defined a new type of number — like the Peano numbers:

data Peano = Zero | Succ Peano deriving Eq

Note that this type definition is almost identical to the kind we would write in F#, except that the “deriving” piece at the end specifies that the compiler should automatically put this type into the “Eq” type-class (allowing Peano values to be compared for equality).

In order to treat these structures as numbers (to put the “Peano” type into the “Num” type-class), we need to define each function required by the Num type-class:

instance Num Peano where
   p + Zero              = p
   p + (Succ x)          = (Succ p) + x
   p – Zero              = p
   Zero – x              = Zero
   (Succ p) – (Succ x)   = p – x
   p * Zero              = Zero
   p * (Succ x)          = (p * x) + p
   abs p                 = p
   signum Zero           = 0
   signum p              = 1
   fromInteger 0         = Zero
   fromInteger n | n > 0 = Succ (fromInteger (n – 1))

Here, we’ve implemented the “+”, “-”, and “*” operators by the standard definitions of Peano numbers.  The rest of the functions aren’t very interesting, but are required to make this Num Peano instance consistent with all uses of numbers in Haskell.

We can then test this definition in a fairly straightforward way, opening a GHC prompt with the above type/instance initialized (to do this, put the above definitions in a file, peano.hs, and then run: ghci peano.hs):

Prelude> let one = Succ Zero
Prelude> let two = Succ one
Prelude> let three = Succ two
Prelude> (one + two) == three
True

Our existing functions, defined only over instances of the Num type-class, will also work with this new form of number:

Prelude> (twice one) == two
True

If this kind of first-order ad-hoc polymorphism were added to F#, it would go a long way toward restoring some of the honest (logically consistent) conveniences of languages like C++ (or Haskell, for that matter).  But that’s not all that type-classes can do.  In the next article, I’ll show how they also subsume more language features, like inheritance and sub-typing, in an equally rigorous and logically consistent way.

7 Responses to “The F# overload-o-phone”

  1. Kishor Aher Says:

    Also operators are not special in haskell and they are not built into the language, Its just an ordinary function. Haskell provides ‘short circuit’ evaluation without any special support.

  2. Rick Minerich's Development Wonderland : Discoveries This Week 03/20/2009 Says:

    [...] Blog – Kalani Thielen’s The F# overload-o-phone [...]

  3. Carsten Says:

    Sure you are right – F# would benefit from some Haskell features.
    But I would first demand type classes (you might need them too ;) )

    I try using F# as much as possible (I just like functional languages and this is the first one with real life support :) ) and the stuff you descripe never was a problem to me.

    As far as I know (+) does not represent the +-operator (there is not THE + – operator in the CLR and yep F# is just “fancy” CLR) but a function int -> int -> int – so why int and not ‘a -> ‘a -> ‘a
    Well this is a problem: for ‘a -> ‘a -> ‘a you need some things for the ‘a type – for example the existenz of the + – operator, existence of a zero might be needed in some other context etc.
    But you just can’t do this in .NET – there is no IArithmetic interface and there are no type classes.
    You can go and implement such a interface yourself and live happy afterwards but than you have to implement int, float, etc. by your self again to gain support for your interface.
    This is a issue know since .net 2.0 and I think there I a huge demand for an interface in the last – but I don’t think we will see this until 5.0 or later (not planned for the 4.0 release as far as I know)

    BTW: you can overload functions in F# – you just have to give the compiler a new name for them ( just use [] in front of your function/method/constructor/whatever )

  4. Functional Arithmetic Redux » Lab49 Blog Says:

    [...] Last time we compared arithmetic overloading and type-inference in F# and Haskell.  We even created our own numeric type in Haskell, as represented by Peano numbers, by implementing a type-class instance.  This stood in contrast to F#’s fixed set of numeric types (whose overloading of arithmetic functions was treated as a special case by F#’s type-checker). [...]

  5. Ganesh Sittampalam Says:

    You can do let inline twice x = x + x to get the overloaded type (and twice will then be inlined at every call site). It’s not a very well documented F# feature because it’s really intended for the library and I don’t think it’s guaranteed to be maintained in exactly this form.

  6. Kalani Thielen Says:

    Ganesh,

    That’s interesting, and it would solve the problem of writing functions that can do arithmetic either on floats or ints. Unfortunately it wouldn’t let you extend the definition of a “number” though — so you couldn’t say that a tuple of numbers is itself a number (ie: “twice (1, 2)” wouldn’t work).

  7. Ganesh Sittampalam Says:

    Actually you just need to define a static member (+) on any type you like for it to work. You might be able to do it for existing types like tuples through extensions, but I’m not sure about that.