- From: Sandro Hawke <sandro@w3.org>
- Date: Mon, 04 May 2009 13:40:45 -0400
- cc: Jos de Bruijn <debruijn@inf.unibz.it>, RIF <public-rif-wg@w3.org>
[reply to myself]
> This functions-are-functions thing is worrying me, too. This means list
> "union", "intersect", and "except" need to be defined with stable
> ordering, I think, which I believe means they're stuck with n^2
> algorithms. Is it really impossible to allow for non-determinism /
> non-specification on these things? I had been expecting the order of
> lists returned from these operations to be undetermined (which would
> allow an implementation to really use hash tables to b-trees behind the
> scenes.) Hmmm, I guess there are tricks one could still do -- add a
> list-index field, and then sort the final result by that field -- but
> ouch....
After a little more thought, maybe this isn't a real problem. I guess
it's okay to define them with stable ordering.
(What I'm thinking is that folks who don't care about the ordering will
do operations on the result that don't care about the order (like
checking membership, or more of these set-style operations), and in that
situation -- which can be recognized -- faster set-style operations can
be implemented. Of course, none of that really matters if we don't
parameterize equality-checking/compare.)
-- Sandro
Received on Monday, 4 May 2009 17:40:53 UTC