Split a list into two parts with a given length

Question

I'm learning Common Lisp as a hobby and am trying tasks from L-99: Ninety-Nine Lisp Problems, but I'm not sure how good my code is. Here is one of the tasks which I solved:

GitHub solution

;;; (*) Split a list into two parts; the length of the first part is given.
;;; Do not use any predefined predicates.
;;;
;;; Example:
;;; * (split '(a b c d e f g h i k) 3)
;;; ((A B C) (D E F G H I K))
(defun split (given-list cnt &optional (result-left nil))
 (if (= cnt 0)
 (if (null result-left)
 given-list
 (cons result-left (list given-list)))
 (if (null given-list)
 result-left
 (split (cdr given-list) (- cnt 1) (append result-left (list (car given-list)))))))

Answer 1

Let’s use a completely different approach: first try to solve the problem using predefined (complex) functions, then implement those functions with the primitive ones (recursion, car, cdr, etc.)

So, how could be solved your problem in Common Lisp with predefined functions? I would suggest this simple solution (note the use of values instead of list to return two different values);

CL-USER> (defun split (list count)
 (values (subseq list 0 count) (nthcdr count list)))
SPLIT
CL-USER> (split '(A B C D E F G) 3)
(A B C)
(D E F G)

In other words, copy the first count values from the list to a new list with subseq (reference), then simply return the elements of the list starting from count with nthcdr (reference).

Or, if you prefer to use a single predefined function, with the following definition we make also a copy of the second part of the list (which is not strictly necessary):

(defun split (list count)
 (values (subseq list 0 count) (subseq list count)))

Now let's assume subseq it is not predefined and try to implement my-subseq with just recursion and primitive functions:

(defun copy-to-end (l end)
 "copy the list l from beginning to the element at position end - 1"
 (if (zerop end)
 nil
 (cons (car l) (copy-to-end (cdr l) (1- end)))))
(defun my-subseq (l start &optional (end (length l)))
 "copy the list l from the element at position start to the element at position end - 1"
 (if (zerop start)
 (copy-to-end l end)
 (my-subseq (cdr l) (1- start) (1- end))))

So the final function will be:

(defun split (list count)
 (values (my-subseq list 0 count) (my-subseq list count)))

It is left as an exercise to define my-nthcdr with recursion and primitive functions to implement my first version of the function split.

Answer 2

Public interface

I wouldn't expose the result-left argument to the public. It is simply not meant for the user of the function to be used in any way. Thus, I'd (削除) defun (削除ここまで) use labels to define an "inner" function inside of split.

Don't append. cons and then nreverse

When you append to a list, then that list needs to be fully traversed. Moreover, append creates a new list, creating significant garbage since you don't need the lists passed to it anymore after the call.

Same structure of return value

When I run your split with

(print (split '(A B C) 1))
(print (split '(A B C) 0))
(print (split '() 2))
(print (split '(A) 4))

then I get

((A) (B C)) 
(A B C) 
NIL 
(A) 

but for consistency I would expect the result to be a list of two elements, the first being the part that was split off, the second being the rest of the list. Thus I'd expect a result like this:

((A) (B C)) 
(NIL (A B C)) 
(NIL NIL) 
((A) NIL) 

Don't recur, iterate.

Common Lisp has no guarantee for tail call optimization. Thus recursion might get expensive even if the recursive calls are in tail call position. To avoid this you can write your code in an iterative manner, e.g. using do.

---

For reference: My recursive solution based on your code. Can probably be improved much further.

(defun split (list after)
 (labels
 ((inner (first-part remaining second-part)
 (if (= 0 remaining)
 (values first-part second-part)
 (if (null second-part)
 (values first-part second-part)
 (inner (cons (first second-part) first-part)
 (1- remaining)
 (rest second-part))))))
 (multiple-value-bind (first-part second-part) (inner '() after list)
 (list (nreverse first-part) second-part))))

Furthermore, iterative version:

(defun split (list after)
 (do ; variables
 ((remaining after (1- remaining))
 (first-part nil (cons (first second-part) first-part))
 (second-part list (rest second-part)))
 (; end test
 (or (= remaining 0) (null second-part))
 ; result
 (list (nreverse first-part) second-part))
 ; empty body
 ))

• Shmygol: Wow! Thank you very much for your time. I've upvoted your answer, let's see weather some more nice suggestions comes, which is not very likely for Common Lisp though :). And I have some questions: 1. You suggest never use append. Why there is one than? As a python developer I expect some optimization on interpreter level. Isn't it the case? 2. "Common Lisp has no guarantee for tail call optimization.". Really? It would be very disappointing. Where can I read more about tail call optimization in Common Lisp. Thanks!
• Daniel Jour: Tail call optimization: 0branch.com/notes/tco-cl.html Though I don't know how up-to-date this list is
• Daniel Jour: append is useful if you want a copy of the original list. I'm still wondering for an example, though ...