Monday, January 19, 2009

Generalized curry in F#

When coding in F#, you really get used to the automatic currying the language provides. It feels just natural. However, F# lives within the .NET world, so sooner or later, you have to call some function from the BCL or another assembly you have coded in C#. Problem is, F# maps the method parameters as tuples, so they are uncurried. Let's take for example String.Compare(string,string). When coding in F#, its signature is (string * string) -> int so you have to call it just like you would in C#:

String.Compare("something", "something else")

If it were curried, its signature would be string -> string -> int, so you could call it like this:

String.Compare "something" "something else"

This little difference can get quite annoying. It feels like an "exceptional" call when you have to put the parens.

Of course, it's not arbitrary that F# doesn't automatically curry every function in the framework. For example, curried functions are actually implemented with FastFuncs, so String.Compare would have to be wrapped in a function that took a string and returned a FastFunc<string, int> closure which in turn calls the actual String.Compare. No such thing as a free lunch :-)

So I set out to either find or develop a way to curry any function.

Looking for inspiration in other languages, I found that generalized currying can be done fairly easily in dynamic languages like LISP, Scheme, Javascript, Ruby. As an aside note, I was quite surprised that Matz treated currying in Ruby as an "easter egg for functional programming kids". (?)

In statically typed languages it's more complicated. The difference seems to be that arity isn't a concept as strong in dynamic languages as it is in statically typed ones. In C#, although not a mainly functional language, generalized currying can be implemented by creating different overloads of a curry function, one for each arity. Haskell has its own set of solutions, which I'll someday understand but not today :-)

I asked on hubFS, it seems that there isn't anything standard yet for F#. So I tried to use method overloading to overcome the arity problem. The result is this boring code, similar to Dustin's solution:

type FP =
    static member curry2 (f:_*_ -> _) = 
        fun a b -> f (a,b)

    static member curry (f:_*_ -> _) = 
        FP.curry2 f

    static member curry3 (f:_*_*_ -> _) = 
        fun a b c -> f (a,b,c)
    static member curry (f:_*_*_ -> _) = 
        FP.curry3 f
    static member curry4 (f:_*_*_*_ -> _) = 
        fun a b c d -> f (a,b,c,d)

    static member curry (f:_*_*_*_ -> _) = 
        FP.curry4 f
    static member curry5 (f:_*_*_*_*_ -> _) = 
        fun a b c d e -> f (a,b,c,d,e)

    static member curry (f:_*_*_*_*_ -> _) = 
        FP.curry5 f
    static member curry6 (func:_*_*_*_*_*_ -> _) = 
        fun a b c d e f -> func (a,b,c,d,e,f)

    static member curry (func:_*_*_*_*_*_ -> _) = 
        FP.curry6 func

But this has problems when trying to curry overloaded methods:

  • FP.curry String.Compare doesn't work, since the compiler doesn't know which overload to pick. (there are ten overloads!)
  • FP.curry2 String.Compare works fine, since we are explicitly telling the compiler the arity of the method, and there is only one overload with two parameters; however:
  • FP.curry3 String.Compare fails, because there are two overloads of String.Compare with three parameters.

Conclusion: this is not a good way to implement generic currying in F#. It would be very nice to have this integrated into the language, but I wouldn't hold my breath. As a workaround, I'll consider implementing a post-build step using Mono.Cecil to create the necessary FastFunc wrappers.

No comments: