Recursive split-list function LISP

Question

The split-list function takes a list and returns a list of two lists consisting of alternating elements of the input. I wrote the following:

(defun split-list (L)
  (cond
      ((endp L) (list NIL  NIL))
      (t (let ((X (split-list (cdr L))))
         (cond
             ((oddp (length L))
              (list (cons (first L) (first X)) (cadr X)))
             (t (list (first X) (cons (first L) (cadr X)))))))))

The output is as expected for odd numbered lists, the first list consisting of the 1st, 3rd, 5th etc elements and the second part consisting of the 2nd, 4th, 6th etc. With an even list however, the 1st, 2nd ,3rd.. are on the right of the returned lists with the rest on the left.

For Example:

(SPLIT-LIST '(a b c 1 2 3))
(SPLIT-LIST RETURNED ((b 1 3) (a c 2))

the order should be swapped. Is there a major flaw in my logic that I'm missing? Can I rectify this situation without making major alterations?

Answer 1

Yes, you can rectify the problem without major modifications.

1. Add a case for (endp (cdr L))
2. Do the recursive call on cddr L
3. After that, the else case will always have two new elements, one to cons onto each list; there is no more need for the length call

Answer 2

One of the very common idioms in recursive list processing is to build up result lists in reverse order, and then to reverse them just before returning them. That idiom can be useful here. The essence of your task is to return a list of two lists, the first of which should contain even-indexed elements, the second of which should contain odd-indexed elements. Here's how I'd approach this problem (if I were doing it recursively). The idea is to maintain a list of even elements and odd elements, and a boolean indicating whether we're at an even or odd position in the overall list. On each recursion, we add an element to the "evens" list, since the current index of the current list is always zero, which is always even. The trick is that on each recursive call, we swap the evens and the odds, and we negate the boolean. At the end, we use that boolean to decide which lists are the "real" evens ands odds list.

(defun split-list (list &optional (evens '()) (odds '()) (evenp t))
  "Returns a list of two lists, the even indexed elements from LIST
and the odd indexed elements LIST."
  (if (endp list)
      ;; If we're at the end of the list, then it's time to reverse
      ;; the two lists that we've been building up.  Then, if we ended
      ;; at an even position, we can simply return (EVENS ODDS), but
      ;; if we ended at an odd position, we return (ODDS EVENS).
      (let ((odds (nreverse odds))
            (evens (nreverse evens)))
        (if evenp
            (list evens odds)
            (list odds evens)))
      ;; If we're not at the end of the list, then we add the first
      ;; element of LIST to EVENS, but in the recursive call, we swap
      ;; the position of EVENS and ODDS, and we flip the EVENP bit.
      (split-list (rest list)
                  odds
                  (list* (first list) evens)
                  (not evenp))))

CL-USER> (split-list '())
(NIL NIL)
CL-USER> (split-list '(1))
((1) NIL)
CL-USER> (split-list '(1 2))
((1) (2))
CL-USER> (split-list '(1 2 3))
((1 3) (2))
CL-USER> (split-list '(1 2 3 4))
((1 3) (2 4))
CL-USER> (split-list '(1 2 3 4 5 6 7 8 9 10))
((1 3 5 7 9) (2 4 6 8 10))

Answer 3

First, when you have cond with only one test and a default t clause, please use if instead. Also, you are using first, but cadr; second is more readable in your context than cadr.

Now, the order is swapped for even lists. Try to perform a step-by-step execution. It might be a little tedious by hand but this is useful to understand what happens. I personally prefer to use the trace macro: (trace split-list). Then, running your example:

   0: (split-list (a b c 1 2 3))
    1: (split-list (b c 1 2 3))
      2: (split-list (c 1 2 3))
        3: (split-list (1 2 3))
          4: (split-list (2 3))
            5: (split-list (3))
              6: (split-list nil)
              6: split-list returned (nil nil)
            5: split-list returned ((3) nil)
          4: split-list returned ((3) (2))
        3: split-list returned ((1 3) (2))
      2: split-list returned ((1 3) (c 2))
    1: split-list returned ((b 1 3) (c 2))
  0: split-list returned ((b 1 3) (a c 2))

Unclear? Try with an odd-sized list:

   0: (split-list (a b c 1 2))
    1: (split-list (b c 1 2))
      2: (split-list (c 1 2))
        3: (split-list (1 2))
          4: (split-list (2))
            5: (split-list nil)
            5: split-list returned (nil nil)
          4: split-list returned ((2) nil)
        3: split-list returned ((2) (1))
      2: split-list returned ((c 2) (1))
    1: split-list returned ((c 2) (b 1))
  0: split-list returned ((a c 2) (b 1))

It seems you always store the innermost result in the left list!

A possible recursive implementation goes roughly like this:

(defun split-list (list)
  (if (endp list)
      '(nil nil)
      (destructuring-bind (left right) (split-list (cddr list))
        (list (cons (first list) left)
              (if (second list)
                  (cons (second list) right)
                  right)))))

But this can blow the stack for sufficiently large inputs. For your information, here is a simple non-recursive approach with loop:

(defun split-list (list)
    (loop for (a b) on list by #'cddr
          collect a into left
          when b 
            collect b into right
          finally (return (list left right)))

And since you probably will have to split your list into more than 2 lists in your next assignment, a more generic version, still with loop:

(defun split-list (list &optional (n 2))
  (loop with a = (make-array n :initial-element nil)
        for e in list
        for c = 0 then (mod (1+ c) n)
        do (push e (aref a c))
        finally (return (map 'list #'nreverse a))))

(split-list '(a b c d e f g) 3)
=> ((a d g) (b e) (c f))

If you want to have fun with circular lists, you can also try this, which works for any sequence, not only lists:

(defun split-n (sequence &optional (n 2))
  (let* ((ring (make-list n :initial-element nil))
         (head ring)
         (last (last ring)))
    (setf (cdr last) ring)
    (map nil
         (lambda (u)
           (push u (first ring))
           (pop ring))
         sequence)
    (setf (cdr last) nil)
    (map-into head #'nreverse head)))

If you plan to investigate how this works, evaluate (setf *print-circle* t) first.