[Haskell-cafe] Re: mathematical notation and functional programming
Henning Thielemann
lemming at henning-thielemann.de
Fri Jan 28 14:16:59 EST 2005
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.
More information about the Haskell-Cafe
mailing list