[Haskell-cafe] Re: mathematical notation and functional programming

On Fri, 28 Jan 2005, Chung-chieh Shan wrote:

Henning Thielemann wrote in article in gmane.comp.lang.haskell.cafe:

...

Over the past years I became more and more aware that common mathematical notation is full of inaccuracies, abuses and stupidity. I wonder if mathematical notation is subject of a mathematical branch and whether there are papers about this topic, e.g. how one can improve common mathematical notation with the knowledge of functional languages.

I would like to know too!

But I would hesitate with some of your examples, because they may simply illustrate that mathematical notation is a language with side effects -- see the third and fifth examples below.

I can't imagine mathematics with side effects, because there is no order of execution.

...

Things I'm unhappy about are for instance f(x) \in L(\R) where f \in L(\R) is meant

(I'm not sure what you are referring to here -- is there a specific L that you have in mind?)

Erm yes, my examples are taken from functional analysis. L(\R) means the space of Lebesgue integrable functions mapping from \R to \R.

...

F(x) = \int f(x) \dif x where x shouldn't be visible outside the integral

(Not to mention that F(x) is only determined up to a constant.)

right, so \int needs a further parameter for the constant

...

O(n) which should be O(\n -> n) (a remark by Simon Thompson in The Craft of Functional Programming)

I'm worried about this analysis, because would O(1) mean O(\n -> 1), and 1/O(n^2) mean 1/O(\n -> n^2)?

O(n^2) means O(\n -> n^2), yes. People say, it is obvious what O(n^2) means. For me it is obvious that they probably want to pass a constant function in, because O takes a function as argument and because I know people often don't distinguish between constant functions and scalar values. Then O(n) = O(n^2) because O(n) and O(n^2) denote the set of constant functions. :-) But what do you mean with 1/O(n^2) ? O(f) is defined as the set of functions bounded to the upper by f. So 1/O(f) has no meaning at the first glance. I could interpret it as lifting (1/) to (\f x -> 1 / f x) (i.e. lifting from scalar reciprocal to the reciprocal of a function) and then as lifting from a reciprocal of a function to the reciprocal of each function of a set. Do you mean that?

And what about the equal sign in front of most uses of big-O notation?

This must be an \in and this prevents us from any trouble.

I would rather analyze this notation as

O = shift k. exists g. g is an asymptotically bounded function and k(g(n))

where "shift" is Danvy and Filinski's control operator (paired with "reset"). This way, we can use (as people do)

reset(f(n) = 2^{-O(n)})

to mean that

exists g. g is an asymptotically bounded function and f(n) = 2^{-g(n)*n}.

I never heard about shift and reset operators, but they don't seem to be operators in the sense of higher-order functions.

With some more trickery underlying the equal sign, one can state meanings such that "O(n) = O(n^2)" is true but "O(n^2) = O(n)" is false.

Sticking to the set definition of O we would need no tricks at all: O(\n -> n) \subset O(\n -> n^2) and O(\n -> n) /= O(\n -> n^2)

...

a < b < c which is a short-cut of a < b \land b < c

What do you think of [a,b,c] for lists?

I learnt to dislike separators like commas, because 1. (practical reason) it's harder to reorder lists in a editor 2. (theoretical reason) it's inconsistent since there is always one separator less than list elements, except when the list is empty. In this case there are 0 separators instead of -1. So I think (a:b:c:[]) is the better notation.

...

f(.) which means \x -> f x or just f

I regard this as reset(f(shift k. k)). Besides, even Haskell has (3+).

Hm, (3+) is partial application, a re-ordered notation of ((+) 3), which is only possible if the omitted value is needed only once. But I see people writing f(.) + f(.-t) and they don't tell, whether this means (\x -> f x) + (\x -> f (x-t)) or (\x -> f x + f (x-t)) In this case for most mathematicians this doesn't matter because in the above case (+) is silently lifted to the addition of functions. It seems to me that the dot is somehow more variable than variables, and a dot-containing expression represents a function where the function arguments are inserted where the dots are.

...

All of these examples expose a common misunderstanding of functions, so I assume that the pioneers of functional programming also must have worried about common mathematical notation.

But AFAIK, nobody ever promised that the mathematical notation used to talk about functions must denote functions themselves.

I found that using a notation respecting the functional idea allows very clear terms. So I used Haskell notation above to explain, what common mathematical terms may mean.