Re: How do lisp gurus truncate?

[Giorgos Keramidas]

On Thu, 23 Jul 2009 08:32:56 +0200, Lennart Borgman <lennart.borgman@gmail.com> 
wrote:
> I want to truncate an ordered list if the rest of the values are
> bigger than some limit. I just wrote some code like this one to do
> that, but there must be some more standard way of doing that, or?
>
>           (when nxml-where-first-change-pos
>             (setq nxml-where-path 'dummy nxml-where-path)
>             (let ((path nxml-where-path))
>               (while (cdr path)
>                 (when (> (nth 1 (nth 1 path)) nxml-where-first-change-pos)
>                   (setcdr path nil))
>                 (setq path (cdr path))))
>             (setq nxml-where-path (cdr nxml-where-path)))

I'd probably use `every' to perform the test and start iterating over
the list at the first location returned by `member' or `find', i.e. from
a CLISP session:

    [9]> (every (lambda (number)
                  (> number 3))
                (list 4 5 6))
    T

    [10]> (member 3 (list 1 2 3 4 5 6 7))
    (3 4 5 6 7)

    [11]> (every (lambda (number)
                   (> number 3))
            (rest (member 3 (list 1 2 3 4 5 6 7 8 9))))
    T

Locating the first item that is probably easier to do with `find' than
with `member', because it lets you find the first number *larger* than
the value you are looking for, i.e.:

    [25]> (find 3 (list 1 2 3 4 5 6 7) :test #'<)
    4

Since you are looking for the nth-cdr minus 1, you can find the location
of the first item larger than 3 with:

    (let ((mylist (list 1 2 3 4 5 6 7))
          (item 3))
      (let ((first-large-item (find item mylist :test #'<)))
        (when first-large-item
          (nthcdr (1- first-large-item) mylist))))
    => (4 5 6 7)

This is easy to pass to `every' then:

    (let ((mylist (list 1 2 3 4 5 6 7))
          (item 3))
      (let ((first-large-item (find item mylist :test #'<)))
        (when first-large-item
          (every (lambda (number)
                   (> number item))
            (nthcdr (1- first-large-item) mylist)))))
    => T

Using *that* result with the (nthcdr (- first-large-item 2) mylist) to
setcdr the CDR of the appropriate cons cell is probably easy then.  In
Common Lisp, using (setf (cdr ...)) the code would look like this:

    [37]> (defun trim-sorted-list (item sequence)
            (let ((first-large-index (find item sequence :test #'<)))
              (when first-large-index
                (let ((last-node (nthcdr (- first-large-index 2) sequence)))
                  (when (every (lambda (number)
                                 (> number item))
                               (cdr last-node))
                    (setf (cdr last-node) nil)
                    sequence)))))
    TRIM-SORTED-LIST

    [38]> (trim-sorted-list 3 (list 1 2 3 4 5 6 7))
    (1 2 3)

    [39]> (trim-sorted-list 8 (list 1 2 3 4 5 6 7))
    NIL

A similar function for Emacs Lisp, using (setcdr ...) would look like
this, I guess:

    (defun trim-sorted-list (item sequence)
      (let ((first-large-index (find item sequence :test #'<)))
        (when first-large-index
          (let ((last-node (nthcdr (- first-large-index 2))))
            (when (every (lambda (number)
                           (> number item))
                         (cdr last-node))
              (setcdr last-node nil)
              sequence)))))

My only concern about find/nthcdr is that if the list can get very very
long, you are essentially going to iterate over it twice.  But I am not
sure if there's a function like `find' that will return the cons cell
instead of the value at position N.