[Haskell-cafe] mathematical notation and functional programming

Hamilton Richards ham at cs.utexas.edu
Fri Jan 28 23:05:08 EST 2005

At 9:14 PM +0100 2005/1/27, Henning Thielemann wrote:
>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.

Your distaste for common mathematical notation was shared by Edsger
W. Dijkstra. For a sampling of his writings on the subject, visit
http://www.cs.utexas.edu/users/EWD/welcome.html and search the
transcriptions for "notation". Or use the Advanced Search" facility
to pick up other forms such as "notations" and "notational".

>
>Things I'm unhappy about are for instance
>
>f(x) \in L(\R)
>    where f \in L(\R) is meant
>
>F(x) = \int f(x) \dif x
>    where x shouldn't be visible outside the integral
>
>O(n)
>    which should be O(\n -> n) (a remark by Simon Thompson in
>                                The Craft of Functional Programming)

I use lambda notation extensively in the part of my discrete math
course that deals with complexity. Works fine.

Moreover --anticipating a reply further down the list-- my students
learn that O(f) for some function f denotes a set of functions, so
that f = O(g), where f and g are functions of the same type, is
simply a type error. I seem to recall that Donald Knuth made this
point a few decades ago, but old habits die hard.

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

This problem has worse consequences when the operator is (=). By
common convention,

a = b = c is shorthand for a = b /\ b = c

which is a great mistake because it obscures the extremely valuable
(for equational reasoning) fact that when a, b, and c are Boolean,
(=) is associative.
In their textbook, _A Logical Approach to Discrete Math_, Gries
and Schneider explain that (=) is conjunctional, and that an operator
can't be both conjunctional and associative. Following Dijkstra, they
introduce another operator, the equivalence (=) (that should display
as a three-bar equality operator). It's defined only for Boolean
operands, and it's not conjunctional but associative.

>f(.)
>    which means \x -> f x or just f
>
>
>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.

As did Dijkstra, who devoted the last part of his career to "the
streamlining of mathematical argument".

Regards,

--Ham