Anonymous Functions in Math and CS

Consider:

f(x) = ...

This is how one normally declares a function in math: by describing what the value of the function applied to a variable would be. One consequence of this approach is that ir necessitates a variable name, in this case f, being assigned to the function.

This may not sound significant or problematic, but consider what the parallel of this in a different class of objects, like numbers would be. Before doing anything, we’d have to assign a variable to the number! For example, we couldn’t just write 3*2, we’d have to write x=2; y=3; x*y. This may still not seem significant. After all, it’s only functions; people only have to define them occasionally.

I’d like to mention a theory that someone (Kelly Rose, one of the leaders — read teachers — of hacklab.to‘s math reading group) mentioned to me recently, that the reason two people (Newton and Leibniz) effectively simultaneously discovered calculus after people failed to for however many thousand years was that notation had developed that allowed for the discovery. (Interesting side note: this individual suggested that category theory may be the next big change.)

If this is theory is correct (and I’m not sure how we could every be certain) then it is the best example I can think of, of something I’ve been thinking about for several weeks: the importance of notation. (I’m using the term `notation’ loosely as including something that isn’t truly a new idea but is a new way of presenting the idea.)

It seems obvious to me that if one makes an idea difficult to represent, a person will avoid using it (or make an easier way to represent it). In some ways, this is applying the Sapir-Whorf hypothesis to things other than spoken language: the medium (traditional language, visualisation, notation, etc) of thinking effects the thoughts themselves. (If you’ve been nodding along, consider the effects English must be having on you mind; you may now wish to look at Lojban.)

I believe this is true, to an extent that I am probably failing to convey. (It’s why, for example, I find it deeply troubling that \pi isn’t defined as 2\pi: think about all the students who would have had a better understanding of trigonometry and more respect for math in general if it wasn’t for the fact that Pi Is Wrong.)

But we’ve digressed. Back to functions. We need to ask, is there a way to avoid defining a variable when using functions. In fact there is: x \to .... For example, the following to statements are identical:

f(x)=x^2+3; f(2)

(x\to x^2+3)(2)

We call (x\to x^2+3) an anonymous function. Another notation for this is using lambda calculus. We represent a function with \lambda x. ~ .... For example, the earlier example would be (\lambda x . x^2+3).

This has endless usefullness in math. It can provide an ellegant way to represent the Mandelbrot set, for example:

\left\{x\in \mathbb{C}| \lim_{n\to\infty}(z\to z^2+x)^n(x)\neq\pm\infty\right\}

Translation for non-mathematicians: the set of complex numbers x such that if we square x, add x, square that and add x, and so on infinitely, we won’t end up with infinity.

We can also use this to define functions that return functions using it. For example, we can define the differential operator, \frac{d}{dx}:

\frac{d}{dx}(f) = (x \to \lim_{h\to 0} \frac{f(x+h)-f(x)}{h})

We can also use anonymous functions in programing. For example, python allows us to use lambda calculus in it. The following is perfectly valid:

>>> (lambda x: x*x +3)(2)
7

Now, you may have noticed that we can do some really interesting things with this. And could do even more interesting things, if we could make recursive functions.

Some programing languages support anonymous recursive functions. For example, in javascript, functions are passed a `callee’ argument that allows one to recurse on itself. Thus, we can implement an anonymous function that gives us a term in the Fibonacci sequence.

(function (x) {
  if (x <= 2) {
    return 1;
  } else {
    return arguments.callee(x - 1) + arguments.callee(x - 2);
  }
})(6) // = 8

More on this is available here.

But what about in math? There doesn’t seem to be a well defined notation for anonymous recursive functions in math… So, I’ve had to invent my own.

In lambda calculus, I’ve always perceived the lambda to be a place holder for the function. So, I’m rather fond of the notation \lambda x = .... If one uses that notation, it’s a small step to use a lambda on the other side of the the equals sign…

We can use this notation to do some very cool things. For example, we can use this to make the Cantor set:

\left(\lambda s = \lambda \left[m(s),\frac{2*m(s)+M(S)}{3}\right] \cup \lambda \left[\frac{m(s)+2*M(S)}{3},M(s)\right]\right)[0,1]

Translation for non-mathematicians: Take the line segment from 0 to 1, remove the middle third, then remove the middle third from the remaining pieces, and so on infinitely.

Of course, this notation does run into problems when one wants to have nested lambda calculus, but this can be fixed by using subscripts, ie \lambda_1, \lambda_2, ~....

About these ads

Tags: , ,

7 Responses to “Anonymous Functions in Math and CS”

  1. Formation of Escape-Time Fractals « Christopher Olah’s Blog Says:

    [...] of the Mandelbrot set is . (If this is notation confuses you, you may wish to refer to my previous post on anonymous functions.) Iteration [...]

  2. Sniffnoy Says:

    I should probably point out, the standard notation for anonymous functions in math uses \mapsto (|->), not \rightarrow (->). (\rightarrow indicates domain and target space, \mapsto indicates action on points. Thus f:R->R, but f:x|->x^2. Or f=(x|->x^2) if we want to use anonymous functions.) But this is a minor point.

    The “\lambda s =…” notation I find to be problematic. We’re notating an anonymous function, right? The whole expression should be a function. But if you write “\lambda s=…”, now it looks like an equation, not an object. Lambda really isn’t a name; its name is… well, the function itself. I’m not convinced that recursive anonymous functions are helpful, really; they seem to be more trouble than they’re worth. I suppose if you really wanted to do this for some reason you could always do it like in actual lambda calculus and use a fixpoint combinator! It might not make sense technically but the meaning should be clear. Honestly I’d just avoid it though.

    • christopherolah Says:

      > I should probably point out, the standard notation for anonymous functions in math uses \mapsto (|->), not \rightarrow (->).

      Very true. This is from a while ago, I was eventually corrected.

      > I suppose if you really wanted to do this for some reason you could always do it like in actual lambda calculus and use a fixpoint combinator! It might not make sense technically but the meaning should be clear. Honestly I’d just avoid it though.

      TIL what a fixed point combinator is.

    • christopherolah Says:

      > I should probably point out, the standard notation for anonymous functions in math uses \mapsto (|->), not \rightarrow (->).

      Very true. This is from a while ago, I was eventually corrected.

      > I suppose if you really wanted to do this for some reason you could always do it like in actual lambda calculus and use a fixpoint combinator! It might not make sense technically but the meaning should be clear. Honestly I’d just avoid it though.

      TIL what a fixed point combinator is. Thanks!

  3. Ethan Jaffe Says:

    So that’s what they’re called…
    Thanks for finally giving them a name!

    • christopherolah Says:

      You’re welcome! It’s kind of funny that you were looking for a name, since I spent a great deal of time espousing the greatness of anonymous functions back in grade 12 :)

  4. a Says:

    i am also crazy about inefficiency of the math notation.
    You should check javascript based ASCIImath to MathML website. ASCII math is much better than LATEXmath

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 465 other followers

%d bloggers like this: