## Re: [Series-users] How to write series-tail

 Re: [Series-users] How to write series-tail From: Chris Dean - 2005-12-15 08:01:27 ```Chris Dean writes: > How do I write a function to return the last N elements of a series? > I'd prefer that the result of this function be a series itself. Here's one way. Assume a ring data structure and only keep the last N elements: (defun series-tail (items how-many) "Returns the last HOW-MANY elements of the series ITEMS. If HOW-MANY is greater than (collect-length ITEMS) then all of the elements in ITEMS are returned." (declare (optimizable-series-function 1) (off-line-port items)) (let ((ring (make-ring how-many))) (iterate ((x items)) (ring-enqueue ring x)) (scan-ring ring))) I eagerly await a code critique. If found this very difficult to write, mostly due to the cryptic (to me) error messages. However, once it was done it looks very nice and elegant. Using series-tail makes the series expression not parallelizable which is expensive, but no more expensive than another non-series looping construct. (The ring code is below for those interested.) Regards, Chris Dean ;;; ;;; rings ;;; (defstruct (ring (:constructor make-ring-storage)) size index current-length vec) (defun make-ring (size) "Create a ring. A ring is like a fixed sized queue except that when the ring is full and an element is inserted, the oldest element is deleted to make room. SIZE is the size of the ring." (make-ring-storage :size size :index 0 :current-length 0 :vec (make-array size))) (defun ring-enqueue (ring obj) "Add a new element to the ring. The oldest element in the ring may be deleted to make room." (with-slots (size index current-length vec) ring (setf (svref vec index) obj) (setf index (mod (1+ index) size)) (setf current-length (min size (1+ current-length))) obj)) (defun ring-dequeue (ring) "Remove the oldest element from the ring. It is an error to remove from an empty ring." (when (ring-empty? ring) (error "ring is empty")) (prog1 (ring-ref ring 0) (decf (ring-current-length ring)))) (defun ring-ref (ring i) "Get the element at the index I. The oldest element is index 0." (with-slots (size index current-length vec) ring (let ((ii (mod (+ i (- index current-length)) size))) (svref vec ii)))) (defun ring-empty? (ring) (zerop (ring-current-length ring))) (defun ring-full? (ring) (= (ring-current-length ring) (ring-size ring))) (defun scan-ring (ring) "Return the ring as a series." (declare (optimizable-series-function)) (let ((i 0) (len (ring-current-length ring))) (scan-fn t (lambda () (and (/= i len) (ring-ref ring i))) (lambda (x) (declare (ignore x)) (ring-ref ring (incf i))) (lambda (x) (declare (ignore x)) (= i len))))) (defun ring->list (ring) "Convert the ring to a list" (collect (scan-ring ring))) ```

 [Series-users] How to write series-tail From: Chris Dean - 2005-12-13 03:01:06 ```[Looks like I'm on a roll with all these questions!] How do I write a function to return the last N elements of a series? I'd prefer that the result of this function be a series itself. Here's one way that doesn't really work: (defun series-tail (items &optional (how-many 1)) (declare (optimizable-series-function 1)) (let ((len (collect-length items))) (if (<= 0 how-many len) (subseries items (- len how-many)) items))) I suppose I could keep a ring of the last HOW-MANY elements, but I'm not sure how to do that. Thanks again! Regards, Chris Dean ```
 Re: [Series-users] How to write series-tail From: - 2005-12-13 13:54:57 ```>>>>> "Chris" == Chris Dean writes: Chris> [Looks like I'm on a roll with all these questions!] Chris> How do I write a function to return the last N elements of a series? Chris> I'd prefer that the result of this function be a series itself. Chris> Here's one way that doesn't really work: Chris> (defun series-tail (items &optional (how-many 1)) Chris> (declare (optimizable-series-function 1)) Chris> (let ((len (collect-length items))) Chris> (if (<= 0 how-many len) Chris> (subseries items (- len how-many)) Chris> items))) I don't think you can do that because you don't know how long the series is until you traverse it. I suppose you could keep a list of the last N elements as you traverse it so you have the last N at any point as you traverse the list, but I suspect this isn't what you really want. Ray ```
 Re: [Series-users] How to write series-tail From: Chris Dean - 2005-12-15 08:01:27 ```Chris Dean writes: > How do I write a function to return the last N elements of a series? > I'd prefer that the result of this function be a series itself. Here's one way. Assume a ring data structure and only keep the last N elements: (defun series-tail (items how-many) "Returns the last HOW-MANY elements of the series ITEMS. If HOW-MANY is greater than (collect-length ITEMS) then all of the elements in ITEMS are returned." (declare (optimizable-series-function 1) (off-line-port items)) (let ((ring (make-ring how-many))) (iterate ((x items)) (ring-enqueue ring x)) (scan-ring ring))) I eagerly await a code critique. If found this very difficult to write, mostly due to the cryptic (to me) error messages. However, once it was done it looks very nice and elegant. Using series-tail makes the series expression not parallelizable which is expensive, but no more expensive than another non-series looping construct. (The ring code is below for those interested.) Regards, Chris Dean ;;; ;;; rings ;;; (defstruct (ring (:constructor make-ring-storage)) size index current-length vec) (defun make-ring (size) "Create a ring. A ring is like a fixed sized queue except that when the ring is full and an element is inserted, the oldest element is deleted to make room. SIZE is the size of the ring." (make-ring-storage :size size :index 0 :current-length 0 :vec (make-array size))) (defun ring-enqueue (ring obj) "Add a new element to the ring. The oldest element in the ring may be deleted to make room." (with-slots (size index current-length vec) ring (setf (svref vec index) obj) (setf index (mod (1+ index) size)) (setf current-length (min size (1+ current-length))) obj)) (defun ring-dequeue (ring) "Remove the oldest element from the ring. It is an error to remove from an empty ring." (when (ring-empty? ring) (error "ring is empty")) (prog1 (ring-ref ring 0) (decf (ring-current-length ring)))) (defun ring-ref (ring i) "Get the element at the index I. The oldest element is index 0." (with-slots (size index current-length vec) ring (let ((ii (mod (+ i (- index current-length)) size))) (svref vec ii)))) (defun ring-empty? (ring) (zerop (ring-current-length ring))) (defun ring-full? (ring) (= (ring-current-length ring) (ring-size ring))) (defun scan-ring (ring) "Return the ring as a series." (declare (optimizable-series-function)) (let ((i 0) (len (ring-current-length ring))) (scan-fn t (lambda () (and (/= i len) (ring-ref ring i))) (lambda (x) (declare (ignore x)) (ring-ref ring (incf i))) (lambda (x) (declare (ignore x)) (= i len))))) (defun ring->list (ring) "Convert the ring to a list" (collect (scan-ring ring))) ```
 Re: [Series-users] How to write series-tail From: - 2005-12-19 15:35:50 ```>>>>> "Chris" == Chris Dean writes: Chris> [Looks like I'm on a roll with all these questions!] Chris> How do I write a function to return the last N elements of a series? Chris> I'd prefer that the result of this function be a series itself. Chris> Here's one way that doesn't really work: Chris> (defun series-tail (items &optional (how-many 1)) Chris> (declare (optimizable-series-function 1)) Chris> (let ((len (collect-length items))) Chris> (if (<= 0 how-many len) Chris> (subseries items (- len how-many)) Chris> items))) Chris> I suppose I could keep a ring of the last HOW-MANY elements, but I'm Chris> not sure how to do that. Not sure if this is exactly what you want, but here is a function that takes a series and returns a new series whose elements are a list of the last N elements seen thus far. (defun series-tail (items how-many) (declare (optimizable-series-function 1)) (#Mreverse (collecting-fn t #'(lambda () (make-list 0)) #'(lambda (r x) (values (subseq (cons x r) 0 how-many) (cons x r))) items))) (series-tail (scan-range :below 10) 3) => #Z((0) (0 1) (0 1 2) (1 2 3) (2 3 4) (3 4 5) (4 5 6) (5 6 7) (6 7 8) (7 8 9)) And if you really want the last set, then (collect-last (series-tail (scan-range :below 10) 3)) => (7 8 9) or even (scan (collect-last (series-tail (scan-range :below 10) 3))) if you want a series. This implementation does generate quite a bit of garbage because it does cons up new lists for each iteration. Ray ```