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 [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
