Re: MEM, DEL, & Co.

[James R. Meehan <Meehan at YALE>]

    Looks fun.  Some points:

    I don't understand the use of "->" at all.  To me, FIND->TAIL would be a
    routine which takes a FIND as its argument, and coerces it somehow to be
    a TAIL.  To give it this new meaning (and I couldn't figure out how that
    meaning is much different from "-") seems a very bad overloading to me.

All the FIND-functions search through tails.  FIND->TAIL returns a
tail, FIND->POS returns a position, etc.  I had it as FIND-TAIL
originally, but that really sounds like a direct object, as if we were
looking for that.  FIND-TAIL wasn't so bad, but FIND-POS, FIND-PRED,
and FIND-SEL didn't sound right at all.  FIND-TAIL->TAIL,
FIND-TAIL->POS, etc., seem unwieldy.  Dunno; I'm open to suggestions.

    I don't see how FIND->TAIL or FIND->SEL generalize, as you say
    they do, to the case of N lists.  Which of the N tails or values
    do you choose to return?

All of them. The output should be isomorphic to the input.

(DEFINE (FIND->TAIL PRED SEL . LISTS)
  (COND ((ANY-NULL-LIST? LISTS) NIL)    ;Can't use ANY, since ANY uses us.
        ((APPLY PRED (MAP SEL LISTS)) LISTS)
        (ELSE (APPLY FIND->TAIL PRED SEL (MAP CDR LISTS)))))

(DEFINE (FIND->PRED PRED SEL . LISTS)
  (COND ((ANY-NULL-LIST? LISTS) NIL)
        ((APPLY PRED (MAP SEL LISTS)))
        (ELSE (APPLY FIND->PRED PRED SEL (MAP CDR LISTS)))))

(DEFINE (FIND->POS PRED SEL . LISTS)
  (DO ((LISTS LISTS (MAP CDR LISTS))
       (N 0 (1+ N))
       (FLAG (ANY-NULL-LISTS? LISTS) (ANY-NULL-LIST? LISTS)))
      ((OR FLAG (APPLY PRED LISTS)) (IF FLAG NIL LISTS))))

(DEFINE (FIND->SEL PRED SEL . LISTS)
  (IF (ANY-NULL-LISTS? LISTS) NIL
      (LET ((X (MAP SEL LISTS)))
           (COND ((APPLY PRED X) X)
                 (ELSE (APPLY FIND->SEL PRED SEL (MAP CDR LISTS)))))))

Examples:
(DEFINE (MEM PRED OBJ . LISTS)
  (APPLY FIND->TAIL
         (LAMBDA SELS (APPLY PRED OBJ SELS))
         CAR LISTS))

(DEFINE (APPEND . LISTS)
  (COND ((NULL? LISTS) '())
        ((NULL? (CDR LISTS)) (CAR LISTS))
        (ELSE ((TRAVERSE (APPLY APPEND (CDR LISTS)) CONS CAR) (CAR LISTS)))))

(ANY PRED SEL . LISTS) <=> (FIND->PRED PRED CAR . LISTS)

(SUBSET < '(1 2 3 4 5) '(10 -11 12 -13 14)) =>
  ((1 10) (3 12) (5 14))

    These should probably become generic routines on sequences, not just
    lists.  Thus CAR and CDR become HEAD and TAIL, etc.  But this has some
    efficiency problems.

True, but maybe it's better to describe them that way.

    Efficiency questions should be addressed somehow; clearly you wouldn't
    want to use the code you gave directly, at least not without extensively
    hacking the compiler.  (Of course I wouldn't have expected this in your
    proposal; just something to think about.)

Yeah, I thought that it would give the compiler fits (CONSing closures?) as
well as being slow.  Does the compiler curry?  Does DEFINE-INTEGRABLE mean
that it treats the definition as a macro so that it can optimize?  The
"real" implementation can cheat by not using TRAVERSE, etc. I mean, that's
a lot of hair just for LENGTH.

    I think the reason I've avoided working on this problem is that
    I wanted to overcome the efficiency problems first.  This is similar
    to what I had in mind, though.

OK.  Well, if you like the lexpr-versions of the FIND-functions (and if I
can find the lexpr-version of TRAVERSE in my notes), how about if I put
them in the LISTS chapter and say that these things are equivalent to
the following definitions?  The implementation can do whatever it needs
until the efficiency problems get solved. The only other function I need
is the modified COMPOSE (for non-unary functions); was that OK?
-------