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

[Dylan Thurston]

(Resurrecting a somewhat old thread...)

On Fri, Jan 28, 2005 at 08:16:59PM +0100, Henning Thielemann wrote:
> On Fri, 28 Jan 2005, Chung-chieh Shan wrote:
> > 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.

Not all side effects require an order of execution.  For instance,
dependence on the environment is a side effect (in the sense that it
is related to a monad), but it does not depend on the order of
execution.  There are many other examples too, like random variables.

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

I don't think this can be right.  Ken argued around this point, but
here's a more direct argument: in

  f(x) = x + 1 + O(1/x)

all the 'x's refer to the same variable; so you shouldn't go and
capture the one inside the 'O'.

This is established mathematical notation, it's very useful, and can
be explained almost coherently.  The one deficiency is that we should
interpret 'O' as "an asymptotically bounded function of..." but that
doesn't say what it is a function of and where we should take the
asymptotics.  But the patch you suggest doesn't really help.

> 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?

I think this is the only reasonable generalization from the
established usage of, e.g., 2^(O(n)).  In practice, this means that
1/O(n^2) is the set of functions asymptotically bounded below by
1/kn^2 for some k.

> 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))

Have you really seen people use that notation with either of those
meanings?  That's really horrible and inconsistent.  I would have
interpreted f(.) + f(.-t) as

 \x \y -> f(x) + f(y-t)

to be consistent with notation like .*. , which seems to mean
 \x \y -> x*y
in my experience.

> 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.

Right.  I don't know how to formalize this, but that doesn't mean it
can't be done.

Peace,
	Dylan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20050203/611481d6/attachment.bin