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