Return list without last element in common lisp

Question

I wrote my silly function which returns a list without the last element in common lisp. Is there any more elegant solution to this problem?

Here's my code:

(defun list-without-last (l)
  (if (> (length (rest l)) 0)
      (append (list (first l)) (list-without-last (rest l)))
      nil))

Cuesta

Answer 1

Your function has two problems:

• you are using LENGTH. LENGTH has to scan the whole list.

• you are using APPEND. Try to use CONS. CONS is simpler.

Common Lisp also already provides this function. It is called BUTLAST.

In real code we also would not use recursion. The stack size would limit the length of lists we can process.

An iterative version using the LOOP macro:

CL-USER> (defun my-butlast (list)
           (loop for l on list
                 while (rest l)
                 collect (first l)))
MY-BUTLAST                                                                                                                                      
CL-USER> (compile 'my-butlast)
MY-BUTLAST                                                                                                                                      
NIL                                                                                                                                             
NIL                                                                                                                                             
CL-USER> (my-butlast '(1 2 3 4 5))
(1 2 3 4)                                                                                                                                       
CL-USER> (my-butlast '(1))
NIL                                                                                                                                             
CL-USER> (my-butlast '(1 2))
(1)                                                                                                                                             

Mchenry

thanks a lot for butlast, btw, what's the problem with append? – Cuesta

APPEND has to scan the entire list, as well as copy all the elements. If you call APPEND multiple times in a loop, you end up with a function that gets exponentially slower as you add more elements. – Becht

@Elias Mårtenson: Append does not copy the last list. – Mchenry

May want to ammend the recursion comment to at least make mention of tail call optimization. Recursion works just fine in "real code", as long as you know what you're doing. – Caslon

@Caslon tail call optimisation is not in any way required by Common Lisp. Compilers can choose to not do it, and often deliberately will not if debug settings are enabled. One cannot so easily trace a tail recursive function. Scheme style recursion for iteration is not typical of Common Lisp because it is not guaranteed to be iterative and loop usually works completely fine. – Hebbel

Answer 2

Short and simple, just like Lisp. Here is the magic stuff:

(defun without-last(l)
    (reverse (cdr (reverse l))))

Woofer

Answer 3

Sometimes you may find yourself needing to modify the list in place rather than making a copy, in which case this may be handy:

(defun butlast! (x)
  (do ((y x (cdr y)))
      ((null (cddr y))
       (and (rplacd y nil) (return x)))))

Leede

Answer 4

As Rainer Joswig mentioned above, you should use the common lisp built-in function butlast.

But, if you still want to see what an efficient recursive version would look like:

(defun butlast2 (list)
  (labels ((butlast2-worker (list result)
             (if (null list)
                 (nreverse result)
                 (let ((element (first list))
                       (rest (rest list)))
                   (if (null rest)
                       (nreverse result)
                       (butlast2-worker rest (cons element result)))))))
    (butlast2-worker list ())))

As long as your lisp implementation supports tail call optimization, this will be converted into a loop. The trick is that whenever butlast2-worker is called, its result will be returned directly, meaning that you don't need to keep track of the arguments/internal variables from previous calls of the function. Which lastly means that you don't need to keep filling the call stack as you would normally do for a recursive function.

Looking at Rainer Joswig's definition, you can see a tremendous difference in size. Behold the power of loop, and learn to use it wisely whenever you can (or better: use iterate http://common-lisp.net/project/iterate/).

Caslon

Note also that this does twice as much work as the iterative solution as it must scan the list twice – Hebbel

Answer 5

What about:

(defun butlast2 (L)
  (if (null (rest L))
    nil
    (cons (first L) (butlast2 (rest L)))
  )
)

Sg

Blows the stack on longer lists, and is not tail recursive so that even tail call optimization does not help. – Rolo

Answer 6

(defun remove-last (lst)
  (do ((l lst (rest l))
       (res '()))
      ((null (rest l)) (nreverse res))
    (push (first l) res)))

Praefect

You can put the res binding with the binding forms of the do form. – Rolo

@Svante, nice, I haven't thought about that. – Praefect