0
$\begingroup$

What it means to curry a function in computer programming?

In the field of computer programming, the word curry is used to describe functions $f$ such that for any positive whole number $n$ the following two things are equivalent:

  1. Calling function $f$ exactly one time on $n$ separate arguments (input)

  2. Calling function $f$ $n$ separate times, with each function call accepting exactly one argument.

  3. Some combination of the above. e.g. the number of calls to $f$ could be $\lfloor \frac{n}{2} \rfloor$

y = f(1, 2, 3, 4, 5)
y = f(1)(2)(3)(4)(5)
y = f(1, 2)(3, 4, 5)
y = f(1, 2, 3, 4)(5)
y = f(1)(2, 3, 4, 5)

One application in computer programming of currying is to construct a tree of functions which return other functions.

For example, one can implement multi-function dispatching in terms of single-dispatching at each level of the tree.


How might we extend this concept of currying a function to the field of mathematics?

A response to this question is a formal definition of a transformation which curries functions.


Please assume that a function, in general, is defined to be a set of ordered pairs.

$\text{There exists }$ $\text{ a set }$ $\mathbb{DOM}(f)$ $\text{ such that }$ $f \subseteq \mathbb{DOM}(f) \times \mathbb{DOM}(f)$
There exists a set named $\mathbb{DOM}(f)$ such that $f$ is a subset of the Cartesian product of $\mathbb{DOM}(f)$ and $\mathbb{DOM}(f)$

Perhaps there exists a set $\mathbb{A}$ and there exists a set $\mathbb{B}$ such that:

$\mathbb{A} \cap \mathbb{B} = \emptyset$

$\mathbb{A} \subseteq \mathbb{D}$.

$\mathbb{B} \subseteq \mathbb{D}$.

However, talking about one set (or domain), $\mathbb{D}$ for a function, is sufficient even if the set of inputs and the set of outputs have no overlap.


For example, consider the example in which we take function $f$ to be a finite subset of the square-root function such as the following:

$f = \begin{Bmatrix}(1, 1), (4, 2), (9, 3), (16, 4)\end{Bmatrix}$

$f = \begin{Bmatrix}(k^{2}, k) \in \mathbb{N}: k \in \{1, 2, 3, 4\} \end{Bmatrix}$

$\forall k \in \{1, 2, 3, 4\}$, $\quad$ $f = \sqrt[2]{k}$


DEFINITION

We define a transformation $\mathbb{T}$ such that:

For any two sets $\mathcal{ELEMS}$ and $\mathcal{TUPS}$, if there exists $k \in \mathbb{N}$ such that $\mathcal{TUPS} = \mathcal{ELEMS}^{k}$ then we have all three of the following properties:
- $\mathcal{TUPS} \subseteq \mathbb{T}(A)$.
- $\forall k \in \mathbb{N}$ $ELEMS^{K} \subseteq \mathbb{T}(A)$
- $\mathcal{ELEMS} \subseteq \mathbb{T}(A)$


Now we wish to define a transformation $\mathbb{K}$ such that for any function $f$, $\mathbb{K}(f)$ is a function such that $f$ is curried.

Let us define $\mathcal{LEFT}(f) = \begin{Bmatrix} a: a \in \mathcal{DOM}(f) \text{ and } \exists b \in \mathcal{DOM}(f) : (a, b) \in f \end{Bmatrix}$

Let us define $\mathcal{RIGHT}(f) = \begin{Bmatrix} b: b \in \mathcal{DOM}(f) \text{ and } \exists a \in \mathcal{DOM}(f) : (a, b) \in f \end{Bmatrix}$

Then, $\mathbb{K}(f)$ is a mapping from $\mathbb{T}\begin{pmatrix}\mathcal{LEFT}(f)\end{pmatrix}$ to $\mathbb{T}\begin{pmatrix}\mathcal{RIGHT}(f)\end{pmatrix}$ such that what exactly?

If $y = f(1, 2, 3, 4)$, then ...

  • $y = \mathbb{K}(f)(1, 2, 3, 4)$
  • $y = \mathbb{K}(f)(1, 2)(3, 4)$
  • $y = \mathbb{K}(f)(1)(2, 3, 4)$
  • $y = \mathbb{K}(f)(1)(2)(3)(4)$
$\endgroup$
2
  • $\begingroup$ It's been a while, but in my experience with curried functions, $f(1,2,3,4)=f_1(1,2)(3,4)=f_2(1)(2,3,4)=f_3(1)(2)(3)(4)$ gives you three different functions $f_1,$ $f_2,$ and $f_3,$ each of which is one way of currying $f.$ (In some languages you can refer to all of these as $f,$ but they really are different functions, just as all people named David are not all the same person.) Usually just one of those functions is wanted for a particular application. Is there really a need for a super-duper curried-every-possible-way-at-once function? $\endgroup$
    – David K
    Mar 11, 2023 at 3:56
  • $\begingroup$ @DavidK No, not really, of course. You just end up with say, the uncurried function $f:\Pi_i A_i\rightarrow B$, as the canonical representative of an equivalence class, which structure is nothing more than a total order on the $i$s. This latter complication adds nothing of interest. As currently written, reordering isn't even allowed, and this reduces even further into "insert $\leq n-1$ dividers between function applications", so a complete binary tree. $\endgroup$
    – obscurans
    Mar 11, 2023 at 20:41

1 Answer 1

3
$\begingroup$

Instead of the heavy notation that you have invented, just look at the fundamental concept of how sets of functions can be expressed as cardinals: $$f:A\rightarrow B$$ can be identified with the exponential $$f:B^A$$ by the simple expedient of listing every single value of $f(x)$ ranging over the domain $A$, hence a $A$-fold Cartesian product of copies of $B$.

Once you understand that, it's simply a matter of noticing that $$\begin{align}A\rightarrow (B\rightarrow C)&\cong(B\rightarrow C)^A \\&\cong\left(C^B\right)^A \\&\cong C^{A\times B} \\&\cong(A\times B)\rightarrow C\end{align}$$ with nothing more than cardinal arithmetic. Don't overcomplicate things.

$\endgroup$
7
  • 4
    $\begingroup$ There’s more to it than just cardinals! These bijections are natural in a precise sense! $\endgroup$
    – Zhen Lin
    Mar 11, 2023 at 2:48
  • $\begingroup$ @ZhenLin Haha true - didn't want to re-complicate it into category theory since cardinal exponentiation is sufficient. $\endgroup$
    – obscurans
    Mar 11, 2023 at 2:54
  • $\begingroup$ When you write $\begin{pmatrix} f:B^A \end{pmatrix}$ did you mean that $\begin{pmatrix} f:B^{\begin{vmatrix}A\end{vmatrix}} \end{pmatrix}$? Usually, exponents on a set are a whole number, such as $1$, $5$ or $198$. Thus, $f:B^A$ is some set $\begin{Bmatrix} \begin{pmatrix} b_{1}, b_{2}, b_{3}, \cdots b_{n-2}, b_{n-1}, b_{n} \end{pmatrix} \in \mathbb{B} \end{Bmatrix}$. It is okay to exponentiate one set by another set if you explain what that means in English, Deuch, Español, 和製漢字, or another natural language. However, without any explanation, the meaning of $B^{A}$ is ambiguous. $\endgroup$ Mar 11, 2023 at 15:13
  • $\begingroup$ @obscurans What is set $C$? You wrote that $f$ is a mapping from set $A$ to set $B$. What on earth is set $C$? You did not define set $C$. $\endgroup$ Mar 11, 2023 at 15:18
  • 1
    $\begingroup$ I explicitly wrote it in the text immediately following: "an A-fold Cartesian product of copies of B", which is a set-theoretically rigorous definition of cardinal exponentiation. Indexing over a set is a standard set-theoretic operation, of which subsets of $\mathbb{N}$ are a standard but not necessary choice. $2^A$ is common notation for the powerset of $A$, not $2^{|A|}$. You may wish to start reading up on the basics of set theory and understanding how mathematics writes proofs, instead of inventing your own notation. $\endgroup$
    – obscurans
    Mar 11, 2023 at 19:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .