On Wed, Mar 28, 2001 at 09:38:59AM -0500, John Porter wrote:
> Mark-Jason Dominus wrote:
> > I have to agree with whoever followed up that this is a really dumb idea.
> Yahbut... (See last paragraph, below).
OK, I'm agreeing with MJD on this one, and it was my idea. There is no easy
way to check for statelessness in all cases.
In some cases you can -- sin($a) <=> cos($b) is obviously stateless (if $a
and $b aren't magic), because it is composed only of stateless primitives.
This runs afoul of the halting problem real quick. Or so I'm told, and I
belive it.
> If the comparison (or key extraction) function is not idempotent,
> that is a much worse situation than simply one of degraded
> performance. It means the result of sort() won't be (or at least
> will not be guaranteed to be) sorted!
My intuition says that it will either be sorted, for a simple def of sorted
($s[i] <= $s[i+1]), or will take infinite time. (The "take infinite time"
is, I assume, the one that made things dump core.)
> > if my_compare(a,b) < 0, and
> > my_compare(b,c) < 0, then it should also be the case that
> > my_compare(a,c) < 0
> Hm. We could call that "relative idempotency", I suppose.
I'd go with "transitive", since this is a property of the comparator, not the
extractor.
If you seperate the comparator and the extractor(s), then the comparator
must be transitive, and the extractors must be internaly stateless.
> But, aaui, it is not a question of the comparison function
> being idempotent, but the key extraction function being so.
aaui?
Hm. Let's define some terms like "idempotency". These are also my
(current) ideas for sub attributes.
Stateless: The function neither depends on state, nor modifies it. This makes
it a pure (IE mathematical) function. f(a) == f(a), and there is no
side-effect. sin() is stateless.
This means the function is memonizeable.
Internaly stateless: f(a) == f(a), but there might be sideefects that do not
effect the return value. printf is internaly stateless (ignoring linenoize
vars).
This is the essencial property of key extractors. Note that all stateless
functions are internaly stateless.
Transitive:
> > if my_compare(a,b) < 0, and
> > my_compare(b,c) < 0, then it should also be the case that
> > my_compare(a,c) < 0
I can't define it better then that. (Though there's more to it then that).
Note that only the sign of the answer is gaurnteed, so it doesn't even have
to be internaly stateless -- but it probably doesn't make sense for it not
to be.
> Give the braindead no head.
You might want to change that to "heed".
-=- James Mastros
--
The most beautiful thing we can experience is the mysterious. It is the
source of all true art and science. He to whom this emotion is a stranger,
who can no longer pause to wonder and stand wrapt in awe, is as good as dead.
-=- Albert Einstein
AIM: theorbtwo homepage: http://www.rtweb.net/theorb/
