[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
set.
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?
-kzm
--
If I haven't seen further, it is by standing in the footprints of giants
More information about the Haskell-Cafe
mailing list