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

Ketil Malde ketil+haskell at ii.uib.no
Fri Jan 28 16:40:57 EST 2005

Chung-chieh Shan <ccshan at post.harvard.edu> writes:

>> O(n)
>>    which should be O(\n -> n) (a remark by Simon Thompson in
>>                                The Craft of Functional Programming)

It's a neat thought, IMHO.  I usually try to quantify the variables
used, making the equivalent of 'let n = .. in O(n)'

> And what about the equal sign in front of most uses of big-O notation? 

This is a peeve of mine; I've always preferred to view O(n) etc. as sets
of functions, so that a particular function can be a *member* of this

Otherwise, you could have:   f=O(n) /\ g=O(n) => f=g  :-)

> With some more trickery underlying the equal sign, one can state
> meanings such that "O(n) = O(n^2)" is true but "O(n^2) = O(n)" is false.

I would rather say that O(n) is a subset of O(n^2).

>> a < b < c
>>    which is a short-cut of a < b \land b < c

What's the problem with this one?

If I haven't seen further, it is by standing in the footprints of giants

More information about the Haskell-Cafe mailing list