How do lisp gurus truncate?

How do lisp gurus truncate?

[Lennart Borgman]

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)))

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.

Re: How do lisp gurus truncate?

[Pascal J. Bourguignon]

Giorgos Keramidas <keramida@ceid.upatras.gr> writes:

> 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.

Too bad you discarded member earlier...  In Common Lisp it takes a
:test argument like find and other functions.  In emacs, a variant
named member* provides the same feature:

(require 'cl)
(member* 3 '(1.5 2.5 3.5 4.5 5.5) :test (function <)) --> (3.5 4.5 5.5)


-- 
__Pascal Bourguignon__

Re: How do lisp gurus truncate?

[Lennart Borgman]

On Thu, Jul 23, 2009 at 7:05 PM, Giorgos
Keramidas<keramida@ceid.upatras.gr> wrote:
> 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.:

Thanks, but I do not know the elements in the list, just that it is
sorted so using find or member does not work as far as I can see.

(Otherwise would of course "member" do the job.)

Re: How do lisp gurus truncate?

[Pascal J. Bourguignon]

Lennart Borgman <lennart.borgman@gmail.com> writes:

> 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)))


(require 'cl)

(defun* nsplit-list-if (predicate list)
  "Modifies the list cutting it just before the first element for which the predicate 
returns true. Returns the cut list and the rest."
  (loop
     for current on (cons nil list)
     while (cdr current)
     when (funcall predicate (cadr current))
     do (return-from nsplit-list-if
          (values list
                  (prog1 (cdr current) (setf (cdr current) nil)))))
  (values list nil))


(nsplit-list-if (lambda (x) (< 3 x)) (list 0 1 2 3 4 5 6 7))
--> ((0 1 2 3) (4 5 6 7))


(defun split-list-if (predicate list)
  "Returns a copy of the list up to the first element for which the predicate
returns true, and the rest of the list."
  (loop
     with result = '()
     for current on list
     do (if (funcall predicate (car current))
            (return (values (nreverse result) current))
            (push (car current) result))
     finally (return (values (nreverse result) nil))))

(split-list-if (lambda (x) (< 3 x)) '(0 1 2 3 4 5 6 7))
--> ((0 1 2 3) (4 5 6 7))


-- 
__Pascal Bourguignon__

Re: How do lisp gurus truncate?

[Giorgos Keramidas]

On Thu, 23 Jul 2009 19:31:29 +0200, pjb@informatimago.com (Pascal J. Bourguignon) wrote:
>Giorgos Keramidas <keramida@ceid.upatras.gr> writes:
>> 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.
>
> Too bad you discarded member earlier...  In Common Lisp it takes a
> :test argument like find and other functions.  In emacs, a variant
> named member* provides the same feature:
>
> (require 'cl)
> (member* 3 '(1.5 2.5 3.5 4.5 5.5) :test (function <)) --> (3.5 4.5 5.5)

Thank you!  I should have look a bit better at the member docs :)