[Haskell-cafe] Re: mathematical notation and functional programming
Henning Thielemann
lemming at henning-thielemann.de
Fri Feb 4 09:08:51 EST 2005
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.
More information about the Haskell-Cafe
mailing list