Currying and confusion

A friend of mine recently said to me "Don't know anything about currying except for food". I'm sure that nearly everyone who reads this blog is familiar with currying functions (and has probably curried a function within the last few hours), but it makes a good blog topic anyway.

"Currying" a function (as opposed to an entrée) is named after Haskell Curry, but he was inspired by a paper by Moses Schönfinkel, and it appears that Gottlob Frege came up with idea. So much for the name.

Pick your favorite binary function. I like "multiply", but any binary function will do. It need not be associative or commutative. As an example, imagine a print-to function that takes a document and a device.

Now consider these unary functions:

(define (multiply-by-five n) (* 5 n))
(define (multiply-by-negative-one n) (* -1 n))
(define (multiply-by-thirty-seven n) (* 37 n))
etc.

There is an obvious pattern here that we can abstract out:

(define (make-multiply-by x) (lambda (n) (* x n))

(define multiply-by-five (make-multiply-by 5))
(define multiply-by-negative-one (make-multiply-by -1))
(define multiply-by-thirty-seven (make-multiply-by 37))

Or, if we use print-to

(define (make-print-to-device device) (lambda (doc) (print-to doc device)))

(define print-to-inkjet (make-print-to-device the-inkjet-printer))
(define print-to-daisywheel (make-print-to-device the-daisy-wheel-printer))

Note the similarity between make-multiply-by and make-print-to-device.

(define (make-multiply-by x) (lambda (n) (* x n))
(define (make-print-to-device device) (lambda (doc) (print-to doc device)))

(define (make-<unary> an-argument)
  (lambda (another-argument) (<binary> an-argument another-argument)))

We can abstract this operation:

(define (make-unary-maker binary-operation)
  (define (make-unary-operation an-argument)
    (lambda (other-argument)
      (binary-operation an-argument other-argument)))
  make-unary-operation)

We have a pile of functions, all similar because they were created with the make- function. And the make- functions are all similar because they were created with make-unary-maker.

This is the meta-operation we call "currying". We take a function of several arguments, decide on some fixed values for some subset of arguments, and return a new function of the remaining, unfixed arguments.

---

Captain Obvious has a few things to say about functions.

A function won't return a value unless you call it.

The cardinality of the set of return values cannot be larger than the cardinality of the set of valid arguments. Functions don't make up values. There can be fewer possible return values than possible valid arguments, but never more.

If two sets are different sizes, then if you try to pair up elements from each set, you'll have some left over.

If we compose two functions and the set of possible output from the first is different in size from the set of possible valid input to the second, then there will either be output from the first that the second cannot accept, or possible inputs to the second that the first cannot produce. The latter case isn't a problem, but in the former case, you'll get an error.

If you "invert" a function, its output becomes input and vice versa.

Since inverse functions (when they exist, that is) are functions, The same constraints on the cardinality of input and output apply, but in the other direction. If you invert a composition, then the valid arguments and results swap roles. If the cardinalities match, we're cool, but if there is a mismatch, we're in the opposite situation of the non-inverse, and what was not an error (i.e. accepting an input that can never be produced) becomes one (i.e. producing a value that cannot be accepted).

If the appropriate cardinalities never increase, you can compose two functions. If the appropriate cardinalities match, you can invert the composition.

---

What does this have to do with currying?

I'm reading a bit about group theory and I chanced upon some exposition that was thick with comments and arguments surrounding the cardinality of various sets and subsets within the group. Once the exposition introduced a number of sets with equal cardinalities, the author pointed out that you can define an invertible function between any two sets with the same cardinality. Since the set of integers and the set of multiply-by- functions have the same cardinality, you could define a function that maps integers to multiply-by- functions. This isn't much of a revelation because that's what we did to get those functions in the first place. After slogging through this, I finally worked out what they were trying to say: "You can curry the binary operation." But they completely avoided the word "curry", and made arguments about set cardinality.

The next paragraph in the exposition was worse. You can curry the other argument to the binary operation. This leads to a completely different set of curried functions over a different set of arguments. Now it ultimately doesn't matter which argument you curry, when all is said and done, both arguments show up and are passed to the binary function. But all the intermediate values are drawn from different sets than if you curried the other way. It takes a very complicated argument about cardinalities to derive that either way of currying will work.