[alexandria-devel] BISECT

[Samium Gromoff]

From: "Nikodemus Siivola" <nikodemus at random-state.net>
> I can't claim I have thought this thru, but I the interface seems a
> bit strange to me. I would have thought that something like the
> following would be a more natural, and maybe even a more flexible
> approach:
> 
> function BISECT value sequence &key start end key

I'll try to defend the more abstract (?) approach I took, and I'll
address the differences you introduced piecemeal, the
sequences-instead-of-numbers first, and immediate-value-instead-of
-discrete/analytic- function specification next.

The specification of BISECT, as you have presented, confines its usage
to sequences. I believe that it constitutes a serious reduction
of generality[1].

To illustrate this, BISECT-SEQUENCE (if you'll allow me to re-nickname
your version) might be easily implemented on top of BISECT,
albeit lacking the prospect of optimisation for the list case,
whereas the opposite is tentatively harder/less efficient to pull off,
as you'd have to evaluate the discrete function for every value of
the argument, to produce the sequence to operate on. Moreover, you'd
have to provide a way to map the value back to the argument of the
discrete function.  

Moving on to the immediate function specification (this might be
a non-traditional way to word this, but I hope it's sufficiently
clear what I mean). Here I perceive another reduction in generality,
even more severe, as there might be discrete functions with no easy
or even reliable way to construct a mapping to a sequence of real numbers,
whereas constructing a discrete function flipping its truth value
at a given real number is indeed trivial.

But I /think/, I can see the usage concern you addressed with your
proposed change to the BISECT's contract. Perhaps we can supply
both the more general BISECT and BISECT-SEQUENCE[2] together?

I guess I'll hold my updated version of the docstring contract
for BISECT, until I hear more of what you think about the issue.


regards, Samium Gromoff

1. Still I can see potential benefits here (there is an obvious
optimisation in the case of lists, for example).

2. BISECT-SEQUENCE as you have provided it, and perhaps
BISECT-SEQUENCE-IF too, a compromise version between BISECT
and BISECT-SEQUENCE, which is to search the sequence for
predicate satisfaction, rather than specific real value.