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

[Henning Thielemann]

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)

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

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.

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

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