Lisp recursion for split-list

Question

(defun split-list (L) 
    (if (endp L)
    '(nil nil)  
     (let ((x (split-list (cdr L)))) 
         (list (cons (car L) (cadr x))(car X))
         )))

This is the code which I have. It works fine:

(split-list '(1 2 3 4 5 6))
((1 3 5) (2 4 6))

But I need an explanation on the recursion part.

When we call the function (split-list (cdr L)) I am sure that it goes from 123456 to 23456. (car L) is 1 and (cadr X) is 3 but how did 5 came there ?

when function did (split-list (cdr L)) didn't the x became 3456 and (cadr x) should be 4 ? which is wrong and same with other half. (car x) should be 3 now which is wrong.

Could anyone please explain ?

Rainer Joswig · Accepted Answer · 2017-03-20 11:59:12Z

4

I would rewrite a recursive split-list as this:

(defun split-list (list) 
  (if (endp list)
      (values nil nil)
    (multiple-value-bind (split1 split2)
        (split-list (rest list))
      (values (cons (first list) split2)
              split1))))

Above uses multiple values. The function returns the split result as two values. We also replace car with first and cdr with rest. The are just better names, but have the same functionality. multiple-value-bind binds the the two values of the recursive split-list call to the variables split1 and split2. The function values returns its two arguments as two values.

In the example below, you can see that the function indeed returns two values:

CL-USER 20 > (split-list '(a b c d e f))
(A C E)
(B D F)

You can trace its execution:

CL-USER 21 > (trace split-list)
(SPLIT-LIST)

CL-USER 22 > (split-list '(a b c d e f))
0 SPLIT-LIST > ((A B C D E F))
  1 SPLIT-LIST > ((B C D E F))
    2 SPLIT-LIST > ((C D E F))
      3 SPLIT-LIST > ((D E F))
        4 SPLIT-LIST > ((E F))
          5 SPLIT-LIST > ((F))
            6 SPLIT-LIST > (NIL)
            6 SPLIT-LIST < (NIL NIL)
          5 SPLIT-LIST < ((F) NIL)
        4 SPLIT-LIST < ((E) (F))
      3 SPLIT-LIST < ((D F) (E))
    2 SPLIT-LIST < ((C E) (D F))
  1 SPLIT-LIST < ((B D F) (C E))
0 SPLIT-LIST < ((A C E) (B D F))
(A C E)
(B D F)

edited Mar 20, 2017 at 11:59

answered Mar 20, 2017 at 11:52

Rainer Joswig

140k11 gold badges230 silver badges357 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ash Over a year ago

Thank you sir! I always get trouble with the bottom half part of the recursion. First half which is getting rid of elements is easy but bottom half. Its little confusing. Great explanation though.

Collectives™ on Stack Overflow

Lisp recursion for split-list

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related