Cómo quitar paréntesis anidados en LISP

Question

¿Cómo puedo eliminar paréntesis anidados de forma recursiva en LISP comunes tales como

(unnest '(a b c (d e) ((f) g))) => (a b c d e f g) 
    (unnest '(a b))     => (a b) 
    (unnest '(() ((((a))))()))  => (a) 

Gracias

Answer 1

Se podría definir como este por ejemplo:

(defun unnest (x) 
    (labels ((rec (x acc) 
    (cond ((null x) acc) 
     ((atom x) (cons x acc)) 
     (t (rec (car x) (rec (cdr x) acc)))))) 
    (rec x nil))) 

Answer 2

Lisp tiene la función remove para eliminar cosas. Aquí utilizo una versión REMOVE-IF que elimina cada elemento para el que un predicado es verdadero. Pruebo si el objeto es un paréntesis y lo elimino si es verdadero.

Si desea eliminar paréntesis, ver esta función:

(defun unnest (thing) 
    (read-from-string 
    (concatenate 
    'string 
    "(" 
    (remove-if (lambda (c) 
       (member c '(#\(#\)))) 
       (princ-to-string thing)) 
    ")"))) 

Tenga en cuenta, sin embargo, como se menciona Svante, uno no suele 'eliminar' paréntesis.

Answer 3

(defun flatten (l) 
    (cond ((null l) nil) 
     ((atom l) (list l)) 
     (t (loop for a in l appending (flatten a))))) 

Answer 4

(defun flatten (l) 
    (cond ((null l) nil) 
     ((atom (car l)) (cons (car l) (flatten (cdr l)))) 
     (t (append (flatten (car l)) (flatten (cdr l)))))) 

Answer 5

Esto es lo que haría:

(ql:quickload "alexandria") 
(alexandria:flatten list) 

que funciona principalmente porque tengo Quicklisp ya instalado.

Answer 6

(defun unnest (somewhat) 
    (cond 
    ((null somewhat) nil) 
    ((atom somewhat) (list somewhat)) 
    (t 
    (append (unnest (car somewhat)) (unnest (cdr somewhat)))))) 

Answer 7

Me doy cuenta de que este es un hilo viejo, pero es uno de los primeros que aparece cuando google lisp aplana. La solución que descubrí es similar a las discutidas anteriormente, pero el formato es ligeramente diferente. Lo explicaré como si fuera nuevo en lisp, como lo era cuando primero busqué en Google esta pregunta, por lo que es probable que otros también lo hagan.

(defun flatten (L) 
"Converts a list to single level." 
    (if (null L) 
     nil 
     (if (atom (first L)) 
      (cons (first L) (flatten (rest L))) 
      (append (flatten (first L)) (flatten (rest L)))))) 

Para los nuevos en lisp, este es un breve resumen.

La siguiente línea declara una función llamada a aplanar con el argumento L.

(defun flatten (L) 

La línea debajo de cheques por una lista vacía.

(if (null L) 

La siguiente línea devuelve nil porque contras ATOM nula declara una lista con una entrada (Atom). Este es el caso base de la recursión y le permite a la función saber cuándo detenerse. La línea después de esto comprueba si el primer elemento en la lista es un átomo en lugar de otra lista.

 (if (atom (first L)) 

Entonces, si lo es, que utiliza recursión para crear una lista aplanado de este átomo combinado con el resto de la lista aplanada que la función va a generar. cons combina un átomo con otra lista.

  (cons (first L) (flatten (rest L))) 

Si no es un átomo, entonces tenemos que acoplar en él, porque es otra lista que puede tener otras listas dentro de ella.

  (append (flatten (first L)) (flatten (rest L)))))) 

La función de agregar adjuntará la primera lista al inicio de la segunda lista. También tenga en cuenta que cada vez que utiliza una función en lisp, debe rodearla con paréntesis. Esto me confundió al principio.

Answer 8

Este es un enfoque basado en acumuladores. La función local % aplana mantiene un acumulador de la cola (a la derecha parte de la lista que ya ha sido aplanada). Cuando la parte que queda por aplanar (dejó parte de la lista) está vacía, devuelve la cola. Cuando la parte que se aplana no es una lista, devuelve esa parte con el prefijo en la cola. Cuando la parte que se va a aplanar es una lista, aplana el resto de la lista (con la cola actual), luego utiliza ese resultado como la cola para aplanar la primera parte de la lista.

(defun flatten (list) 
    (labels ((%flatten (list tail) 
      (cond 
       ((null list) tail) 
       ((atom list) (list* list tail)) 
       (t (%flatten (first list) 
          (%flatten (rest list) 
             tail)))))) 
    (%flatten list '()))) 

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

Answer 9

Sé que esta pregunta es muy viejo pero me di cuenta de que nadie utiliza el empuje/idioma nreverse, por lo que hoy subo aquí.

la función reverse-atomize saca cada "átomo" y lo pone en el output de la próxima llamada. Al final produce una lista aplanada que está hacia atrás, que se resuelve con la función nreverse en la función atomize.

(defun reverse-atomize (tree output) 
    "Auxillary function for atomize" 
    (if (null tree) 
     output 
     (if (atom (car tree)) 
      (reverse-atomize (cdr tree) (push (car tree) output)) 
      (reverse-atomize (cdr tree) (nconc (reverse-atomize (car tree) 
                   nil) 
               output))))) 

(defun atomize (tree) 
    "Flattens a list into only the atoms in it" 
    (nreverse (reverse-atomize tree nil))) 

Así llamando atomize '((a b) (c) d) se parece a esto:

(A B C D) 

Y si tuviera que llamar reverse-atomize con reverse-atomize '((a b) (c) d) Esto ocurriría:

(D C B A) 

La gente como el uso de funciones como push, nreverse, y nconc porque usan menos RAM que sus respectivos cons, reverse y append funciones. Dicho esto, la doble naturaleza recursiva de reverse-atomize viene con sus propias RAM ificaciones.