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

[Henning Thielemann]

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

> Henning Thielemann <lemming at henning-thielemann.de> wrote in article <Pine.LNX.4.44.0501261011020.25777-100000 at peano.math.uni-bremen.de> 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.