Crítica mi Lisp, por favor

Question

He creado una pequeña rutina:

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

Y utilizarlo:

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

Sin embargo, soy muy consciente de mi capacidad de escritura chapuza C++ en cualquier idioma, y ​​me gustaría algún análisis de mi unzip para un buen estilo de Common Lisp.

Answer 1

• En lugar de un bucle a través de los elementos de la lista, se debe utilizar for-each o car y cdr para iterar sobre la lista hasta que esté vacía.
• Yo no lo llamaría unzip porque no es lo contrario de zip.

Editar: Para ser más específicos, espero zip a tomar un par de listas y devolver una lista de pares, por lo que debe tomar unzip una lista de pares y devolver un par de listas. Yo esperaría que se vea como este ejemplo que encontré:

(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

en primer lugar que '()() y son equivalentes, ya lista vacía es la auto evaluación e igual a NIL, y en cualquier caso no es necesario en aquellos LET porque NIL está implícito en `(let (variable) ...) la sintaxis, lo cual es una razón por la que necesita un paréntesis alrededor de la unión cuando se da el valor de partida.

No es que el uso de LET es necesario para este caso. Usando LOOP características más ampliamente esta función se puede escribir como:

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

personalmente prefiero iterate para la mayoría de iteración, utilizando el que se puede escribir como:

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

o incluso:

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

EDITAR: Notas adicionales: El nombre unzip denota convencionalmente una función ligeramente diferente. El nombre del argumento realmente debería ser list, ya que seq sugeriría que la función también toma vectores. Si bien es posible tener funciones que operan en secuencias generalizadas, generalmente no se recomienda, ya que las listas y vectores tienen diferentes características de rendimiento. En particular, el acceso aleatorio a través de NTH es tiempo lineal para listas, lo que significa que casi nunca debería usarlo. Incluso si el costo de tiempo es insignificante, generalmente indica que debe usar una estructura de datos diferente.

Answer 3

Lo único malo que puedo ver es nth. Debería iterar a través de la lista, ya que nth probablemente necesite iterar la lista de todos modos. Olvídate de las matrices y la indexación de matrices :)

Por desgracia, no sé el cómo hacerlo en Lisp, pero en el esquema, usted acaba de utilizar un llamado let.

Answer 4

Una solución recursiva:

(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

Me gustaría resolver este sea con LOOP o con una función recursiva.

Para una solución basada en LOOP, @Ramarren casi lo ha logrado.

Si no es crítico saber lo que venía de incluso los índices y lo que venía de extraña, me gustaría usar algo como:

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

Si es necesario saber lo que venía de índices pares o impares, I' d envuelva ese UNZIP en una función de ayuda que compare el CAR de la lista y el CAAR del valor de retorno. Si son iguales, pásaleslo de vuelta, de lo contrario intercambia las dos listas en la lista de resultados.

Answer 6

Veamos el código:

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

Aquí es una versión para listas:

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

Ejemplo (tenga en cuenta que la indexación es cero basado en la CL, que cambió el ejemplo para que sea menos confuso):

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

Aquí es una versión que espera una lista aún más larga duración y utiliza BUCLE:

(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

La función (nth n list) tiene que recorrer la lista para acceder al enésimo elemento, una (n) la operación O, y se llama O (n) veces en su aplicación, por lo que todo el proceso de O (n^2) . Puede lograr lo mismo en 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

Versión de esquema, solo para prácticas de tiro. :-) (Requiere la función de SRFI 1 fold.)

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

Para cambiar el orden de las listas devueltos (es decir, elementos incluso indexadas-primero), basta con cambiar la #t-#f.

Answer 9

Aquí hay otra solución posible, utilizando la recursividad:

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

En primer lugar, definimos una función de ayuda de cada dos que se lleva todos los demás elementos de una lista. Luego, ejecutamos esta función en la lista original con el primer elemento omitido y en la lista original.

Desventaja: Debido a la recursión, puede acumular desbordamiento para listas grandes. Si debe manejar listas grandes, vea @Vatine para una solución recursiva de cola.

Answer 10

Aquí es una versión bucle que no es sensible a las entradas de longitud impar, es sólo una pequeña variación de la respuesta de @ Huaiyuan, con un añadido cuando la cláusula:

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