Critique my Lisp, please.

Question

Dear all,

I have created a nice little routine:

(defun unzip (seq)
  "Takes an even-length list and breaks it apart by evens/odd index"
  (let ((oddresult '())
    (evenresult '()))
    (loop for n from 0 to (- (length seq) 1) do
      (if (oddp n)
          (push (nth n seq) oddresult)
        (push (nth n seq) evenresult)))
    (list (reverse oddresult) (reverse evenresult))))

And to use it:

CL-USER> (unzip '(1 2 3 4 5 6))
((2 4 6) (1 3 5))

However, I am keenly aware of my ability to writebotch C++ in any language, and would like some analysis of my unzip for good Common Lisp style.

Answer 1

• Rather than looping over the elements of the list, you should use for-each or car and cdr to iterate over the list until it's empty.
• I would not call it unzip because it isn't the opposite of zip.

Edit: To be more specific, I expect zip to take a pair of lists and return a list of pairs, so unzip should take a list of pairs and return a pair of lists. I would expect it to look like this example I found:

(defun unzip (list)
  (let ((a '())
        (b '()))
    (for-each (lambda (i) (push (first i) a) (push (second i) b)) list)
    (values (nreverse a) (nreverse b))))

Answer 2

First note that '() and () are equivalent, since empty list is self evaluating and equal to NIL, and in any case you don't need those in LET because NIL is implied by `(let (variable) ...) syntax, which is a reason why you need a parenthesis around each binding when giving the a starting value.

Not that using LET is necessary for this case. Using LOOP features more extensively this function can be written as:

(defun unzip (seq)
  "Takes an even-length list and breaks it apart by evens/odd index"
  (loop for n from 0
        for element in seq
        if (oddp n)
          collect element into oddresult
        else
          collect element into evenresult
        finally (return (list oddresult evenresult))))

Personally I prefer iterate for most iteration, using which it can be written as:

(defun unzip (seq)
  "Takes an even-length list and breaks it apart by evens/odd index"
  (iter (for element in seq)
        (for n from 0)
        (if (oddp n)
            (collect element into oddresult)
            (collect element into evenresult))
        (finally (return (list oddresult evenresult)))))

or even:

(defun unzip (seq)
  "Takes an even-length list and breaks it apart by evens/odd index"
  (iter (generate element in seq)
        (collect (next element) into evenresult)
        (collect (next element) into oddresult)
        (finally (return (list oddresult evenresult)))))

EDIT: Additional notes: The name unzip conventionally denotes a slightly different function. The argument name should really be list, since seq would suggest the the function also takes vectors. While it is possible to have functions operating on generalized sequences, it is usually not recommended, since lists and vectors have different performance characteristics. In particular, random access through NTH is linear time for lists, which means you should almost never use it. Even if the time cost is insignificant it usually indicates you should be using a different datastructure.

Answer 3

The only bad thing I can see is nth. You should iterate thru the list instead as nth will likely need to iterate the list anyways. Forget about arrays and array indexing :)

Unfortunately, I dont know the how to do that in Lisp, but in Scheme, you would just use a named let.

Answer 4

A recursive solution:

(defun unzip (seq &optional oddresult evenresult)
  (if (null seq)
      (list (reverse oddresult) (reverse evenresult))
    (if (oddp (car seq))
        (unzip (cdr seq) (cons (car seq) oddresult) evenresult)
      (unzip (cdr seq) oddresult (cons (car seq) evenresult)))))

Answer 5

I would solve this either with LOOP or with a recursive function.

For a LOOP-based solution, @Ramarren has pretty much nailed it.

If it's not critical to know what came from even indexes and what came from odd, I'd use something like:

(defun unzip (list &optional acc1 acc2)
   (if seq
       (unzip (cdr list) acc2 (cons (car list) acc1)))
       (list (nreverse acc1) (nreverse acc2))))

If it's necessary to know what came from odd or even indexes, I'd wrap that UNZIP in a helper function that compares CAR of list and CAAR of the return value. If they're the same, pass it back out, otherwise swap the two lists in the result-list.

Answer 6

Let's look at your code:

(defun unzip (seq)
  "Takes an even-length list and breaks it apart by evens/odd index"

 ; you name the variable seq (sequence), but the documentation mentions
 ; only lists. Sequence is in CL an abstraction over lists and vectors. 

 ; also nothing in the code really says that the list needs to be even-length  

  (let ((oddresult  '())
        (evenresult '()))
    (loop for n from 0 to (- (length seq) 1) do  ; you can iterate BELOW         
      (if (oddp n)
          (push (nth n seq) oddresult)    ; <- NTH is inefficient for lists
        (push (nth n seq) evenresult)))   ; <- NTH is inefficient for lists
    (list (reverse oddresult)             ; <- return multiple values
          (reverse evenresult))))

Here is a version for lists:

(defun unzip (list &aux oddresult evenresult (odd t))
  "Takes a list and breaks it apart by evens/odd index"
  (dolist (element list (values (reverse oddresult) (reverse evenresult)))
    (if (setf odd (not odd))
        (push element oddresult)
      (push element evenresult))))

Example (note that indexing is zero based in CL, I changed the example to make it less confusing):

CL-USER 10 > (unzip '(0 1 2 3 4 5))
(1 3 5)
(0 2 4)

Here is a version that expects an even-length list and uses LOOP:

(defun unzip (list)
  "Takes an even-length list and breaks it apart by evens/odd index"
  (loop for (even odd) on list by #'cddr
        collect even into evenresult
        collect odd  into oddresult
        finally (return (values oddresult evenresult))))

Answer 7

The function (nth n list) needs to traverse the list to access the nth element, an O(n) operation, and it's called O(n) times in your implementation, making the whole process O(n^2). You can accomplish the same in O(n):

(defun unzip (list)
  (loop for (x y) on list by #'cddr
        collect x into a
        collect y into b
        finally (return (list a b))))

Answer 8

Scheme version, just for target practice. :-) (Requires SRFI 1's fold function.)

(define (unzip l)
  (define (iter e v)
    (list (not (car v)) (caddr v) (cons e (cadr v))))
  (define (swap-if p a b)
    (if p (list b a) (list a b)))
  (map reverse
       (apply swap-if (fold iter '(#t () ()) l))))

To change the order of the returned lists (i.e., even-indexed elements first), simply change the #t to #f.

Answer 9

Here is another possible solution, using recursion:

(defun unzip (l)
  (labels ((every-other (l) (if l (cons (car l) (every-other (cddr l))))))
    (list (every-other (cdr l)) (every-other l))))

First, we define a helper function every-other that takes every other element from a list. Then, we run this function on the original list with the first item skipped, and on the original list.

Drawback: Due to recursion it may stack overflow for large lists. If it must handle large lists see @Vatine for a tail-recursive solution.