I am a super CL beginner and I am very stumped on the following task:

Define a recursive function shorten that deletes the last n elements from a given list. The function should return the shortened list at the end.

For example:

 (shorten 5 '(1 2 3 4 5 6 7 8 9 10))
 =>
 (1 2 3 4 5)

Maybe there ist someone who could help me.

Thanks a lot!

CodePudding user response：

My plan to do this would be, having p0 pointing at the list's start, go along the list n times and get p2; then use p1 initially equal to p0 and go along the list each time incrementing both p1 and p2 until p2 points at the list's end; then (rplacd p1 nil); and finally return p0.

Adjust the above for the corner cases and off-by-one errors.

The repeated incrementing of the list's "pointers" by (setf p2 (cdr p2)) etc. can be coded with a recursive function instead, by calling it with (cdr p2) as an argument.

CodePudding user response：

Here is an answer based on Will Ness's nice trick. You probably can't submit this as homework. tconc comes from Interlisp, at least its name does.

(defun empty-tconc ()
  ;; make an empty accumulator for TCONC
  (cons nil nil))

(defun tconc (v into)
  ;; destructively add V to the end of the accumulator INTO, return
  ;; INTO
  (if (null (car into))
      (setf (car into) (list v)
            (cdr into) (car into))
    (setf (cdr (cdr into)) (list v)
          (cdr into) (cdr (cdr into))))
  into)

(defun tconc-value (into)
  ;; Retrieve the value of an accumulator
  (car into))

(defun shorten (l n)
  ;; shorten list L by N elements at the end
  (check-type n (integer 0))
  (shorten-loop l l n (empty-tconc)))

(defun shorten-loop (l1 l2 n into)
  (if (zerop n)
      (if (endp l2)
          (tconc-value into)
        (shorten-loop (rest l1) (rest l2) n
                      (tconc (first l1) into)))
    ;; Note (rest '()) is '() in CL, hence this abuse
    (shorten-loop l1 (rest l2) (1- n) into)))

CodePudding user response：

The solution to this problem is a tail-call recursion. That is to say, when we do each step, we call the function, reducing the count and the input list, and updating a result. When we're done, we return the result. We know that we're done because the counter is zero or the input list is exhausted.

(defun shorten (n lst &optional (res '()))
  (if (or (= n 0) (null lst))
      (reverse res)
      (shorten (1- n) (cdr lst) (cons (car lst) res))))

(shorten 5 '(1 2 3 4 5 6 7 8 9 10))    ; (1 2 3 4 5)
(shorten 1 '(1 2 3 4 5 6 7 8 9 10))    ; (1)
(shorten 11 '(1 2 3 4 5 6 7 8 9 10))   ; (1 2 3 4 5 6 7 8 9 10)
(shorten 0 '(1 2 3 4 5 6 7 8 9 10))    ; NIL
(shorten 5 '())                        ; NIL