CODEWITHSUNDEEP
listlispreverse
janvdl
janvdl

Reputation: 300

Reverse first n elements of a list in LISP

Assume I have the list (3 1 4 5 2) with the name "numbers". I am looking for a command that will reverse the list from index 0 up to an arbitrary index, i.e. (reverse numbers 2) which will give the new list as (4 1 3 5 2).

I've tried googling, but could not find a suitable function and I'm too much of a newbie to write the function myself at this stage.

Thank you.

Upvotes: 0

Views: 401

Answers (2)

sds
sds

Reputation: 60084

Simple CL version based on the libary functions:

(defun reverse-first-n (list n)
  (nreconc (subseq list 0 n) (nthcdr n list)))
  1. This is memory-optimal, i.e., it does not allocate unnecessarily:
    • no need to copy the tail, thus nthcdr instead of subseq
    • revappend copies the 1st argument which is a fresh list anyway, so nreconc is more economical.
  2. This version is speed-suboptimal, because it traverses list to the nth position 3 times - once in subseq, once in nthcdr, and then once in nreconc.

Here is the optimal verion:

(defun reverse-first-n (list n)
  (if (or (= n 0) (= n 1))
      list
      (do* ((tail (list (pop list)))
            (head tail (cons (pop list) head))
            (count (1- n) (1- count)))
           ((zerop count)
            (setf (cdr tail) list)
            head))))

Note that there is very little chance that this is the performance bottleneck in your code. My main purpose in providing the second version is to show how much time and effort the extensive and well-designed CL library saves you.

Upvotes: 6

C. K. Young
C. K. Young

Reputation: 223193

Which dialect of Lisp are you using? Here's a Scheme solution (using SRFI 1):

(require srfi/1)    ; assuming you're using Racket
(define (reverse-first-n lst n)
  (call-with-values (lambda ()
                      (split-at lst n))
                    append-reverse!))

I made the function really "reverse the first n elements" like your title says, and unlike your question description. So for example:

> (reverse-first-n '(3 1 4 5 2) 2)
'(1 3 4 5 2)
> (reverse-first-n '(3 1 4 5 2) 3)
'(4 1 3 5 2)

As requested by the OP, here's a Common Lisp version. sds already posted a pretty decent version, so the version I'm writing is a more direct port of my Scheme solution (append-reverse! ⇒ nreconc; call-with-values ⇒ multiple-value-call; and I'm porting SRFI 1's split-at to CL):

(defun split-at (list n)
  (if (zerop n)
      (values '() list)
      (multiple-value-bind (prefix suffix)
                           (split-at (cdr list) (1- n))
        (values (cons (car list) prefix) suffix))))

(defun reverse-first-n (list n)
  (multiple-value-call #'nreconc (split-at list n)))

(Why split-at? Its purpose is to provide both the take (subseq) and drop (nthcdr) with only one traversal of the input list.)

Upvotes: 2

Related Questions