From: KMP@stony-brook.scrc.symbolics.com (Kent M Pitman)
Newsgroups: comp.lang.lisp
Subject: How to find the first n items in a list?
Date: 28 Sep 92 20:58:48 GMT
Organization: LCS news/mail gateway
X-Unparseable-Date: Mon


    Date: Mon, 28 Sep 1992 13:58 EDT
    From: Mark Chang <mchang@bcrka440.bnr.ca>

    For example, I have a long list, '(0 1 2 ..... 9999)
    and I want the first 1000 items as a list, '(0 1 ... 1000).
 
There are several ways to do this.

Efficiency will somewhat depend on whose implementation you're using
since different implementations make different operations fast.

It also depends on what assumptions you are making about how the list is
terminated.  e.g., in both of the following, I'm assuming the list might 
be dotted.

The most common technique which you are most likely to be overlooking is
consing the list up backward and nreversing it.

(DEFUN FIRSTN (LIST N)
  (IF (OR (ATOM LIST) (< N 1))
      LIST
      (DO ((NEW-LIST '() (CONS (CAR L) NEW-LIST))
	   (L LIST (CDR L))
	   (I 0 (1+ I)))
	  ((= I N) (NREVERSE NEW-LIST))
	(WHEN (ATOM L) (RETURN (NRECONC NEW-LIST L))))))

It is possible with a little extra work to do it one-pass forward, but
the disadvantage is that in a multi-processing environment, there may be
intermediate consing in another process the list may get scattered.  Also,
in a cdr-coded implementation, the resulting list will not be cdr-coded.
In fact, in the following, if you do (LIST (CAR LIST)) instead of
(CONS (CAR LIST) NIL) you'll get really bad performance in a cdr-coded
implementation.

(DEFUN FIRSTN (LIST N)
  (IF (OR (ATOM LIST) (< N 1))
      LIST
      (LET ((NEW-LIST (CONS (CAR LIST) NIL)))
	(DO ((I 1 (1+ I))
	     (L (CDR LIST) (CDR L))
	     (TAIL NEW-LIST (CDR TAIL)))
	    ((= I N) NEW-LIST)
	  (COND ((ATOM L)
		 (SETF (CDR TAIL) L)
		 (RETURN NEW-LIST))
		(T
		 (SETF (CDR TAIL) (CONS (CAR L) NIL))))))))

Another technique that relies on your having a good GC and/or a belief
that the N is going to be below the number of elements in the list most of
the time (so you don't throw things away much) is to make the list first 
and then copy elements into it. e.g.,

(DEFUN FIRSTN (LIST N)
  (IF (OR (ATOM LIST) (< N 1))
      LIST
      (LET ((NEW-LIST (MAKE-LIST N)))
	(DO ((L LIST (CDR L))
	     (NL NEW-LIST (CDR NL))
	     (TAIL NIL NL)
	     (I 0 (1+ I)))
	    ((= I N) NEW-LIST)
	  (COND ((ATOM L)
		 (SETF (CDR TAIL) L)
		 (RETURN NEW-LIST))
		(T
		 (SETF (CAR NL) (CAR L))))))))

Here are some test cases that should work for all of these.

(FIRSTN '(A B C D) 2) => (A B)
(FIRSTN '(A B C D) 20) => (A B C D)
(FIRSTN '(A B C . D) 3) => (A B C)
(FIRSTN '(A B C . D) 5) => (A B C . D)
(FIRSTN 'A 3) => A

And, actually, the following should not have really terrible performance.
It doesn't work for dotted or circular lists, though, and it forces the
entire list just to compute its length.  You could write a custom version
of LENGTH that timed out after value N, though, to make back the speed on
that.

(defun firstn (list n) 
  (let ((len (length list)))
    (butlast list (max (min len (- len n)) 0))))

The advantage here is that BUTLAST is probably specially coded to be optimal
at the copying part for the given implementation.