[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Two maybe-bugs and two proposals




Hello Amir,

Thank you for the remarks.

> Actually, it would work iff thereone exactly one class.

You are right; we'll correct it.

> Also, in an impure language such is Scheme, a comparison function
> can be defined from equality - but not in O(1) operations.

We state that already by saying there are no "sublinear worst-case" data structures
for this. I'll rewrite the remark to make it clearer and given an implementation explicitly;
it might prove useful to somebody someday.

> The specification of the chain functions (#node_idx_90) states clearly
> that when exactly one value is given, the comparison function should
> still be invoked. The purpose of this is not clear, since the only
> difference between this comparison and a no-op is type-checking. IMO,
> there is no use for this kind of uniformity here (to me it doesn't seem
> uniform at all).

The purpose of calling the compare procedure for the only element
of  a chain of length one is indeed type-checking: I am not sure what
you mean by "uniformity" here, but after calling

        (apply chain<? compare-integer xs)

you may assume that xs is a list of objects satisfying integer?,
irrespectively of the length of xs or the outcome of the test.
(We'll add a clarifying remark in the specification.)

In my experience, most people will assume that xs is a list of
integers anyhow, no matter what is actually specified for chain<?.
(And we try to minimize the "gotcha potential.")

> I would like the <? family of functions to take only one parameter, the
> comparison function, so that they will transform from comparison
> functions to predicates. This is also doable with srfi-26 as (cut <? <>
> <>), but for many uses, including the second proposal, the shorter form
> is nicer.

>
> Another proposal is to drop the `chain' functions. There is one basic
> higher order list function, (chain pred . elts) that applies the elts in
> consecutive pairs. If the previous proposal is also accepted, all that
> would be required from uses is typing (chain (<? comp) ...) instead of
> (chain<? comp ...). It would also allow non-srfi-67 uses of this list
> function, and using default-compare: (chain <? ...) works as (chain<?
> default-compare ...) does in the document.


Incidentally, we had this design in an earlier (before release) version
of the SRFI and we switched to the current design later.
However, we switched before we had invented IF<? and friends, which
were conceived when I caught myself avoiding (if ((<? compare) x y) ..) in
the reference implementation for minor efficiency concerns and lying to
myself about efficiency in the spirit of "but in the application I will use it."
Now may be the time to revise the earlier decision, as you propose.

The alternatives are: Parametric tests (<? compare x y) vs. higher-order
procedures (<? compare) => predicate.

I would like to think about this first, and come back to it later.

For the chain tests: The five tests currently specified make sense and are
clearly defined and efficient. (chain? (not=? compare) x ...) is very dangerous,
and the need for non-SRFI-67 use of chain testing is hardly an issue. So,
at least I am pretty happy with chain<? and friends and pairwise-not=?.

Sebastian.

P.S. Sorry for copying you email once again below, but Philips uses Lotus Notes....
----
Dr. Sebastian Egner
Senior Scientist Channel Coding & Modulation
Philips Research Laboratories
Prof. Holstlaan 4 (WDC 1-051, 1st floor, room 51)
5656 AA Eindhoven
The Netherlands
tel:       +31 40 27-43166   *** SINCE 10-Feb-2005 ***
fax:      +31 40 27-44004
email: sebastian.egner@xxxxxxxxxxx








srfi-67-request@xxxxxxxxxxxxxxxxx

14-04-2005 13:57

       
        To:        srfi-67@xxxxxxxxxxxxxxxxx
        cc:        (bcc: Sebastian Egner/EHV/RESEARCH/PHILIPS)
        Subject:        Two maybe-bugs and two proposals

        Classification:        




In the question about deriving ordering from equality
(#node_toc_node_sec_Temp_25), it is claimed that the definition doesn't
work if there is more than one element. Actually, it would work iff
thereone exactly one class. Also, in an impure language such is Scheme,
a comparison function can be defined from equality - but not in O(1)
operations.

The specification of the chain functions (#node_idx_90) states clearly
that when exactly one value is given, the comparison function should
still be invoked. The purpose of this is not clear, since the only
difference between this comparison and a no-op is type-checking. IMO,
there is no use for this kind of uniformity here (to me it doesn't seem
uniform at all).

I would like the <? family of functions to take only one parameter, the
comparison function, so that they will transform from comparison
functions to predicates. This is also doable with srfi-26 as (cut <? <>
<>), but for many uses, including the second proposal, the shorter form
is nicer.

Another proposal is to drop the `chain' functions. There is one basic
higher order list function, (chain pred . elts) that applies the elts in
consecutive pairs. If the previous proposal is also accepted, all that
would be required from uses is typing (chain (<? comp) ...) instead of
(chain<? comp ...). It would also allow non-srfi-67 uses of this list
function, and using default-compare: (chain <? ...) works as (chain<?
default-compare ...) does in the document.