1.30. Currying

Consider the following example:
Start C++ section to tut/examples/tut139.flx[1 /1 ]
     1: include "std";
     2: 
     3: fun f4(i4:int): int->int->int->int = {
     4:   fun f3(i3:int): int->int->int = {
     5:     fun f2(i2:int): int->int = {
     6:       fun f1(i1:int): int = {
     7:         return i1+i2+i3+i4;
     8:       }
     9:       return f1 of (int);
    10:     }
    11:     return f2 of (int);
    12:   }
    13:   return f3 of (int);
    14: }
    15: 
    16: print (f4 1 2 3 4); endl;
    17: print ((f4 1 2 3) 4); endl;
    18: print ((f4 1 2) 3 4); endl;
    19: print ((f4 1) 2 3 4); endl;
    20: print (((f4 1) 2 3) 4); endl;
    21: print (((f4 1 2) 3) 4); endl;
    22: 
    23: val curry = f4 1 2;
    24: print (curry 3 4); endl;
    25: 
End C++ section to tut/examples/tut139.flx[1]
You should note that -> is right associative, so that
  int->int->int->int
is equivalent to
  int->(int->(int->int))
On the other hand, application is left associative, so that
  f4 1 2 3 4
is equivalent to
  (((f4 1) 2) 3) 4
Note that the 'partial' applications such as shown by the brackets, are of course closures of the inner functions, and you can use them to initialise values, assign them to variables or pass them to functions. Such 'partial' application is called currying (after the mathematician Howard Curry, who invented the lambda calculus).

While this is a perfectly good defintion, there is a lot of housekeeping going on. Felix provides syntactic sugar that makes it easier to declare functions suitable for currying. Here is the equivalent code, using this sugar:

Start C++ section to tut/examples/tut140.flx[1 /1 ]
     1: include "std";
     2: 
     3: fun f4(i4:int) (i3:int) (i2:int) (i1:int): int = {
     4:   return i1+i2+i3+i4;
     5: }
     6: 
     7: print (f4 1 2 3 4); endl;
     8: print ((f4 1 2 3) 4); endl;
     9: print ((f4 1 2) 3 4); endl;
    10: print ((f4 1) 2 3 4); endl;
    11: print (((f4 1) 2 3) 4); endl;
    12: print (((f4 1 2) 3) 4); endl;
    13: 
    14: val curry = f4 1 2;
    15: print (curry 3 4); endl;
    16: 
End C++ section to tut/examples/tut140.flx[1]
You may remember eariler I said that all Felix accepted exactly one argument, with one exception: tuple constructors.

It is conventional to say that a function like 'f4' above has 4 arguments. Of course, you know that this isn't the case: it really has one argument and returns a function. It is also sometimes said that f4 has arity 4, meaning you can chain applications 4 times, until you get a non-function result.

Note that the notation above can be used for procedures as well: of course, all the partial applications except the last return functions, and the last one returns a procedure.

It is a matter of style whether you write functions in the curried form or not. Any function accepting a tuple can be changed to a currified function accepting the components in sequence. This is conventional in some functional programming languages (like Ocaml), but is less heavily used in others (like SML).

In the current implementation of Felix, currified functions are more expensive than ones accepting tuples, but the currified version is easier to curry :-)

As an exercise, write a function that given an arbitrary function f accepting a tuple of 3 ints, returns an equivalent currified version of it that accepts 3 arguments.

What you have done is called eta-expansion. It is necessary even for currified functions if you want to fix the second argument, but leave the first free.