views:

327

answers:

5

In statically typed functional programming languages, like Standard ML, F#, OCaml and Haskell, a function will usually be written with the parameters separated from each other and from the function name simply by whitespace:

let add a b =
    a + b

The type here being "int -> (int -> int)", i.e. a function that takes an int and returns a function which its turn takes and int and which finally returns an int. Thus currying becomes possible.

It's also possible to define a similar function that takes a tuple as an argument:

let add(a, b) =
    a + b

The type becomes "(int * int) -> int" in this case.

From the point of view of language design, is there any reason why one could not simply identify these two type patterns in the type algebra? In other words, so that "(a * b) -> c" reduces to "a -> (b -> c)", allowing both variants to be curried with equal ease.

I assume this question must have cropped up when languages like the four I mentioned were designed. So does anyone know any reason or research indicating why all four of these languages chose not to "unify" these two type patterns?

+2  A: 

Possibly because it is useful to have a tuple as a separate type, and it is good to keep different types separate?

In Haskell at least, it is quite easy to go from one form to the other:

Prelude> let add1 a b = a+b
Prelude> let add2 (a,b) = a+b
Prelude> :t (uncurry add1)
(uncurry add1) :: (Num a) => (a, a) -> a
Prelude> :t (curry add2)
(curry add2) :: (Num a) => a -> a -> a

so uncurry add1 is same as add2 and curry add2 is the same as add1. I guess similar things are possible in the other languages as well. What greater gains would there be to automatically currying every function defined on a tuple? (Since that's what you seem to be asking.)

ShreevatsaR
Thanks, `curry` and `uncurry` was interesting and I guess they show that this must be possible in principle. The reason I ask is partly stylistics, and partly that currying is one of the main advertised benefits of these languages. This differentiation seems very artificial to me.
harms
+4  A: 

At least one reason not to conflate curried and uncurried functional types is that it would be very confusing when tuples are used as returned values (a convenient way in these typed languages to return multiple values). In the conflated type system, how can function remain nicely composable? Would a -> (a * a) also transform to a -> a -> a? If so, are (a * a) -> a and a -> (a * a) the same type? If not, how would you compose a -> (a * a) with (a * a) -> a?

You propose an interesting solution to the composition issue. However, I don't find it satisfying because it doesn't mesh well with partial application, which is really a key convenience of curried functions. Let me attempt to illustrate the problem in Haskell:

apply f a b = f a b
vecSum (a1,a2) (b1,b2) = (a1+b1,a2+b2)

Now, perhaps your solution could understand map (vecSum (1,1)) [(0,1)], but what about the equivalent map (apply vecSum (1,1)) [(0,1)]? It becomes complicated! Does your fullest unpacking mean that the (1,1) is unpacked with apply's a & b arguments? That's not the intent... and in any case, reasoning becomes complicated.

In short, I think it would be very hard to conflate curried and uncurried functions while (1) preserving the semantics of code valid under the old system and (2) providing a reasonable intuition and algorithm for the conflated system. It's an interesting problem, though.

namin
Thanks, good point. I think the answer must be no, and, yes, I can see a problem with how composition of a->(a*a) with (a*a)->a would work, namely if the latter is a polymorphic function, should it be considered fully applied or just curried?
harms
Although one could conceivably work around this by adding a rule to the type system that the "fullest possible" binding should be the one that gets used.
harms
But how do you resolve "fullest possible" bindings in light of partial application?
namin
I'll make a separate answer with some code examples, then you may point out any glaring errors in my reasoning if you want to :-)
harms
+2  A: 
Chris Conway
Thanks. I know this. My interest was more in going in the other direction, not doing away with tuples but rather using tuple parameter and still being able to partially apply the function.
harms
+2  A: 

Expanding on the comments under namin's good answer:

So assume a function which has type 'a -> ('a * 'a):

let gimme_tuple(a : int) =
    (a*2, a*3)

Then assume a function which has type ('a * 'a) -> 'b:

let add(a : int, b) =
    a + b

Then composition (assuming the conflation that I propose) wouldn't pose any problem as far as I can see:

let foo = add(gimme_tuple(5))
// foo gets value 5*2 + 5*3 = 25

But then you could conceive of a polymorphic function that takes the place of add in the last code snippet, for instance a little function that just takes a 2-tuple and makes a list of the two elements:

let gimme_list(a, b) =
    [a, b]

This would have the type ('a * 'a) -> ('a list). Composition now would be problematic. Consider:

let bar = gimme_list(gimme_tuple(5))

Would bar now have the value [10, 15] : int list or would bar be a function of type (int * int) -> ((int * int) list), which would eventually return a list whose head would be the tuple (10, 15)? For this to work, I posited in a comment to namin's answer that one would need an additional rule in the type system that the binding of actual to formal parameters be the "fullest possible", i.e. that the system should attempt a non-partial binding first and only try a partial binding if a full binding is unattainable. In our example, it would mean that we get the value [10, 15] because a full binding is possible in this case.

Is such a concept of "fullest possible" inherently meaningless? I don't know, but I can't immediately see a reason it would be.

One problem is of course if you want the second interpretation of the last code snippet, then you'd need to go jump through an extra hoop (typically an anonymous function) to get that.

harms
Interesting. I edited my answer to take this into account.
namin
+6  A: 

I think the consensus today is to handle multiple arguments by currying (the a -> b -> c form) and to reserve tuples for when you genuinely want values of tuple type (in lists and so on). This consensus is respected by every statically typed functional language since Standard ML, which (purely as a matter of convention) uses tuples for functions that take multiple arguments.

Why is this so? Standard ML is the oldest of these languages, and when people were first writing ML compilers, it was not known how to handle curried arguments efficiently. (At the root of the problem is the fact that any curried function could be partially applied by some other code you haven't seen yet, and you have to compile it with that possibility in mind.) Since Standard ML was designed, compilers have improved, and you can read about the state of the art in an excellent paper by Simon Marlow and Simon Peyton Jones.

LISP, which is the oldest functional language of them all, has a concrete syntax which is extremely unfriendly to currying and partial application. Hrmph.

Norman Ramsey
Here are two functional languages which prefer tuple form: Nemerle and Scala. Both of which need to integrate with OO languages (as does F#) and want to make their libraries usable from CLR/JVM respectively. Both also permit partial application with syntax like `_ + 3`.
Alexey Romanov
There are Lisps which do partial application as well. Clojure has `#(+ (% 3))` and Scheme has SRFI 26: `(cut + <> 3)`
Alexey Romanov
Thanks for the background, Norman, and the paper which I'll read with interest. And thanks Alexey, for the info on the other languages.
harms
@alexey: shall I edit to add your comments?
Norman Ramsey