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?

Leverage

Programming questions / coding questions are off-topic here, but can be asked on Stack Overflow. – Telltale

calling length on each recursive call is not a good idea. It has to traverse the the list leach time. – Knavery

Recursion is also not a good idea, since it limits the processing by the available stack size. – Knavery

One possibly useful approach would be to move down the list one element at a time, keeping track of "odd or even position" and adding an element to one list or another. – Scary

recursion is always a good idea as a conceptual tool aiding our thinking while developing the solution. once the correct code is formulated, iff your language is limited in its handling of recursion, re-write it to use other means. – Kuenlun

Verbose TXR Lisp: [(juxt (op select @1 (range 0 : 2)) (op select @1 (range 1 : 2))) '(a b c 1 2 3)] -> ((a c 2) (b 1 3)). – Ret

Shorter TXR Lisp: (transpose (tuples 2 '(a b c 1 2 3))). tuples with an argument of 2 shores up consecutive pairs within the list into ((a b) (c 1) (2 3)). Then transpose does exactly what we want (just think of this list of pairs as the columns of a matrix). – Ret

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

Detradetract

Answer 2

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.

Stuff

Answer 3

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))

Scary

Answer 4

Recursion is always a good idea, as a conceptual tool aiding our thinking while developing a problem's solution. Once the correct code is formulated, iff your language is limited in its handling of recursion, re-write it to use other means.

A modern implementation of a Scheme-derived language (Scheme is a kind of a Lisp, right?), Racket has unlimited recursion, implementing call stack on the heap. As such, recursive code for a recursive algorithm is perfectly fine.

Correctness / serenity simplicity first, efficiency later!

The simple solution for your requirements is (in the executable "pseudocode" of Haskell)

    foldr (\x [a, b] -> [x:b, a]) [[], []] 

I first saw this neat trick in an old F# (IIRC) answer by user ed'ka (IIRC); quite a few years back. (But actually it appears to have been in haskellwiki since more or less forever).

Coded in direct recursive style in Scheme, it is

(define (split xs)
  (cond
    ((null? xs) (list '() '()))
    ((split (cdr xs)) => (lambda (acc) 
         (list (cons (car xs) (cadr acc))   ; always in the first subgroup!
               (car acc))))))               

The list's head element must appear in the first subgroup. No need to exert ourselves trying hard to arrange for it to happen, just say it, and it happens just because you said so, all by itself, because of the magic that is recursion !

(split '(a b c 1 2 3))
(split '(a b c 1 2))

; '((a c 2) (b 1 3))
; '((a c 2) (b 1))

A side note: I decided to never use if again, in preference of cond, because an if's clause in itself says nothing about its activation conditions - we must count, of all things, to know which is which. With cond it's plain, and it is right there at the clause's start.

---

It is easy enough to amend this to produce e.g. a three-way split, with

(define (split3 xs)
  (cond
    ((null? xs) (list '() '() '()))
    (else (apply
           (lambda (a b c)             ; Scheme-style destructuring
             (list (cons (car xs) c)   ; rotate right:
                   a                   ;   xs's 2nd elt to appear in the 2nd group!
                   b))                 ;   head element of (cdr xs) is in `a`
           (split3 (cdr xs))))))       ; the recursive result

(split3 '(a b c 1 2 3))
(split3 '(a b c 1 2))

; '((a 1) (b 2) (c 3))
; '((a 1) (b 2) (c))

Kuenlun