[Haskell-cafe] Re: mathematical notation and functional programming

Henning Thielemann lemming at henning-thielemann.de
Mon Feb 7 14:50:54 EST 2005


On Sat, 5 Feb 2005, Dylan Thurston wrote:

> On Fri, Feb 04, 2005 at 03:08:51PM +0100, Henning Thielemann wrote:
>>
>> 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.

Ken? Ken Iverson alias APL? What's meant with continuations?

>  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.

Whereever I have seen a formal definition of O, it is defined to be an
operator with a signature like
 O :: (a -> a) -> Set (a -> a)
  I'm curious how to define an O which takes expressions rather than
values as arguments.

>>>> 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))
>
> I'm curious to see examples.

http://www.math.uni-bremen.de/~teschke/ps/final_formatted.ps.gz

page 6, e.g. the sum symbol in (2.8) and the scalar product in (2.15)



Btw. what did you mean with monadic effects in mathematical notation? When
thinking about using the same symbol or character for different purposes
then I consider this sometimes as scoping issues and sometimes as
overloading. I'm not sure if you meant that.



More information about the Haskell-Cafe mailing list