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

[Dylan Thurston]

On Fri, Feb 04, 2005 at 03:08:51PM +0100, Henning Thielemann wrote:
> On Thu, 3 Feb 2005, Dylan Thurston wrote:
> 
> >On Fri, Jan 28, 2005 at 08:16:59PM +0100, Henning Thielemann wrote:
> >
> >>>>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'.
> 
> I didn't argue, that textually replacing all O(A) by O(\n -> A) is a 
> general solution. For your case I suggest
> 
> (\x -> f(x) - x - 1)   \in   O (\x -> 1/x)

This kind of replacement on the top level is exactly what
continuations (which Ken was suggesting) can acheive.  If you think
carefully about exactly what the big-O notation means in general
expressions like this, you'll be led to the same thing.

> I haven't yet seen the expression 2^(O(n)). I would interpret it as 
> lifting (\x -> 2^x) to sets of functions, then applying it to the function 
> set O(\n -> n). But I assume that this set can't be expressed by an O set.

That's right; for instance, in your terminology, 3^n is in 2^(O(n)).

> >>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?
> 
> In principle, yes.

I'm curious to see examples.

> >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.
> 
> The problems with this notation are: You can't represent constant 
> functions, which is probably no problem for most people, since they 
> identify scalar values with constant functions. But the bigger problem is 
> the scope of the dot: How much shall be affected by the 'functionisation' 
> performed by the dot? The minimal scope is the dot itself, that is . would 
> mean the id function. But in principle it could also mean the whole 
> expression.
>  I think there are good reasons why such a notation isn't implemented for 
> Haskell. But I have seen it in SuperCollider.

I certainly don't want to defend this notation...

Now that you mention it, Mathematica also has this notation, with
explicit delimiters; for instance, `(#+2)&' is the function of adding
two.

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/20050205/16c83f77/attachment.bin