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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
