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