functional programming - Programación funcional: ¿qué es una "lista incorrecta"?
functional-programming erlang (9)
¿Podría alguien explicar qué es una "lista incorrecta"?
Nota : ¡Gracias a todos! ¡Todos ustedes rock!
Creo que es más fácil explicar esto usando Scheme.
Una lista es una cadena de pares que termina con una lista vacía. En otras palabras, una lista termina con un par cuyo cdr es ()
(a . (b . (c . (d . (e . ())))))
;; same as
(a b c d e)
Una cadena de pares que no termina en la lista vacía se llama lista incorrecta. Tenga en cuenta que una lista incorrecta no es una lista. La lista y las notaciones punteadas se pueden combinar para representar listas incorrectas, como muestran las siguientes notaciones equivalentes:
(a b c . d)
(a . (b . (c . d)))
Un ejemplo de un error habitual que lleva a la construcción de una lista incorrecta es:
scheme> (cons 1 (cons 2 3))
(1 2 . 3)
Observe el punto en (1 2. 3) --- que es como el punto en (2. 3), diciendo que el cdr de un par apunta a 3, no a otro par o ''(). Es decir, es una lista incorrecta, no solo una lista de pares. No se ajusta a la definición recursiva de una lista, porque cuando llegamos al segundo par, su cdr no es una lista, es un número entero.
Scheme imprimió la primera parte de la lista como si fuera una lista normal vinculada a cdr, pero cuando llegó al final, no pudo hacer eso, por lo que usó "notación de puntos".
Por lo general, no debería tener que preocuparse por la notación de puntos, ya que debe usar listas normales, no listas incorrectas. Pero si ve un punto inesperado cuando Scheme imprime una estructura de datos, es una buena suposición que utilizó contras y le dio una lista no como su segundo argumento, algo además de otro par o ().
Scheme proporciona un procedimiento útil que crea listas adecuadas, llamadas lista . lista puede tomar cualquier cantidad de argumentos, y construye una lista adecuada con esos elementos en ese orden. No tiene que recordar suministrar la lista vacía --- lista termina automáticamente la lista de esa manera.
Scheme>(list 1 2 3 4)
(1 2 3 4)
Cortesía: una introducción al esquema
Creo que la respuesta de @Vijay es la mejor hasta el momento y solo pretendo Erlangify.
Los pares (celdas cons) en Erlang se escriben como [Head|Tail] y nil se escribe como [] . No hay ninguna restricción en cuanto a lo que son la cabeza y la cola, pero si usas la cola para encadenar más células cons, obtienes una lista . Si la cola final es [] entonces obtienes una lista adecuada . Hay una compatibilidad sintáctica especial para las listas en que la lista adecuada
[1|[2|[3|[]]]]
está escrito como
[1,2,3]
y la lista incorrecta
[1|[2|[3|4]]]
está escrito como
[1,2,3|4]
para que pueda ver la diferencia. Coincidir con listas adecuadas / inadecuadas es, en consecuencia, fácil. Entonces, una función de longitud para las listas adecuadas:
len([_|T]) -> 1 + len(T);
len([]) -> 0.
donde coincidimos explícitamente para la terminación [] . Si se le da una lista incorrecta, esto generará un error. Mientras que la función last_tail que devuelve la última cola de una lista también puede manejar listas incorrectas:
last_tail([_|T]) -> last_tail(T);
last_tail(Tail) -> Tail. %Will match any tail
Tenga en cuenta que crear una lista, o hacer coincidir con ella, como lo hace normalmente con [Head|Tail] no comprueba si la cola está lista, por lo que no hay problema en el manejo de listas incorrectas. Rara vez se necesitan listas inadecuadas, aunque puedes hacer cosas geniales con ellas.
Creo que posiblemente se refiere a un "par de puntos" en LISP, por ejemplo, una lista cuya celda final de cons tiene un átomo, en lugar de una referencia a otra celda de cons o NIL, en el cdr.
EDITAR
Wikipedia sugiere que una lista circular también cuenta como inapropiada. Ver
http://en.wikipedia.org/wiki/Lisp_(programming_language)
y busque ''impropio'' y revise las notas al pie.
En Common Lisp, las listas incorrectas se definen como:
- listas punteadas que tienen un ''átomo'' que no es NIL.
Ejemplo
(a b c d . f)
o
- listas circulares
Ejemplo
#1=(1 2 3 . #1#)
En Erlang, una lista adecuada es aquella donde [H|T] .
H es el jefe de la lista y T es el resto de la lista como otra lista.
Una lista incorrecta no se ajusta a esta definición.
La definición de una lista en Erlang se proporciona en el manual , específicamente en la Sección 2.10.
En Erlang, lo único que realmente necesita saber sobre las listas incorrectas es cómo evitarlas, y la forma de hacerlo es muy simple: se trata de la primera "cosa" en la que va a construir su lista. Todos los siguientes crean listas adecuadas:
A = [].
B = [term()].
C = [term(), term(), term()].
En todos estos casos, la sintaxis garantiza que haya una cola oculta "vacía" que coincide con el tipo ''[]'' al final ...
Entonces, de ellos, las siguientes operaciones producen una lista adecuada:
X = [term() | A].
Y = [term() | B].
Z = [term() | C].
Son todas operaciones que agregan un nuevo encabezado a una lista adecuada.
Lo que hace útil es que puede alimentar a cada uno de X , Y o Z en una función como:
func([], Acc) -> Acc;
func([H | T], Acc) -> NewAcc = do_something(H),
func(T, [NewAcc | Acc]).
Y revisarán la lista y terminarán en la cláusula superior cuando la lista vacía oculta en la cola es todo lo que queda.
El problema surge cuando tu lista base se ha realizado de forma incorrecta, así:
D = [term1() | term2()]. % term2() is any term except a list
Esta lista no tiene la lista vacía oculta como la cola del terminal, tiene un término ...
A partir de aquí, hacia abajo, es picado como lo señaló Robert Virding en los comentarios
Entonces, ¿cómo se escribe una cláusula terminal para ello?
Lo que lo hace irritante es que no hay forma de ver si una lista es incorrecta inspeccionando ... imprima la maldita cosa, se ve bien ... Así que termina creando una lista base incorrecta, haciendo algunas cosas, pasándolo, y de repente kabloowie tienes un accidente a millas de donde está el error y tiras tu cabello y gritas y gritas ...
Pero deberías estar usando el dialyzer para olfatear a estas pequeñas bestias por ti.
Disculpas
Siguiendo el comentario de Robert intenté imprimir una lista incorrecta y, he aquí, es obvio:
(arrian@localhost)5>A = [1, 2, 3, 4].
[1,2,3,4]
(arrian@localhost)5> B = [1, 2, 3 | 4].
[1,2,3|4]
(arrian@localhost)6> io:format("A is ~p~nB is ~p~n", [A, B]).
A is [1,2,3,4]
B is [1,2,3|4]
Había pasado algún tiempo cazando una lista inadecuada una vez y me había convencido de que era inviable, bueno ¡ Ah, no !
Para entender qué es una lista incorrecta, primero debe comprender la definición de una lista adecuada.
Específicamente, el "descubrimiento limpio" de listas es que puede representar una lista utilizando solo formularios con un número fijo de elementos, a saber:
;; a list is either
;; - empty, or
;; - (cons v l), where v is a value and l is a list.
Esta "definición de datos" (utilizando los términos de Cómo diseñar programas) tiene todo tipo de propiedades agradables. Una de las mejores es que si definimos el comportamiento o el significado de una función en cada "rama" de la definición de datos, tenemos la garantía de no perder un caso. Más significativamente, estructuras como esta generalmente conducen a buenas soluciones recursivas limpias.
El clásico ejemplo de "longitud":
(define (length l)
(cond [(empty? l) 0]
[else (+ 1 (length (rest l))]))
Por supuesto, todo es más bonito en Haskell:
length [] = 0
length (f:r) = 1 + length r
Entonces, ¿qué tiene esto que ver con las listas incorrectas?
Bueno, una lista incorrecta usa esta definición de datos, en su lugar:
;; an improper list is either
;; - a value, or
;; - (cons v l), where v is a value and l is an improper list
El problema es que esta definición conduce a la ambigüedad. En particular, el primer y segundo caso se superponen. Supongamos que defino "longitud" para una lista incorrecta de esta manera:
(define (length l)
(cond [(cons? l) (+ 1 (length (rest l)))]
[else 1]))
El problema es que he destruido la buena propiedad de que si tomo dos valores y los coloco en una lista incorrecta con (cons ab), el resultado tiene la longitud dos. Para ver por qué, supongamos que considero los valores (cons 3 4) y (contra 4 5). El resultado es (contras (contras 3 4) (contras 4 5)), que puede interpretarse como la lista incorrecta que contiene (contras 3 4) y (contras 4 5), o como la lista incorrecta que contiene (contras 3 4) , 4 y 5.
En un lenguaje con un sistema de tipos más restrictivo (por ejemplo, Haskell), la noción de una "lista incorrecta" no tiene tanto sentido; podría interpretarlo como un tipo de datos cuyo caso base tiene dos cosas, que probablemente tampoco sea lo que usted desea.
Una lista se compone de celdas, cada celda consta de dos punteros. El primero apunta al elemento de datos, el segundo a la celda siguiente o nulo al final de la lista.
Si el segundo no apunta a una celda (o nada), la lista es incorrecta. Los lenguajes funcionales probablemente le permitirán construir celdas, por lo que debería poder generar listas incorrectas.
En Erlang (y probablemente en otros lenguajes de FP también) puede guardar algo de memoria almacenando sus 2 tuplas como listas incorrectas:
2> erts_debug:flat_size({1,2}).
3
3> erts_debug:flat_size([1|2]).
2
Yo diría que la implicación de una lista incorrecta es que un tratamiento recursivo de la lista no coincidirá con la condición de terminación típica.
Por ejemplo, supongamos que llamas a la siguiente sum , en Erlang, en una lista incorrecta:
sum([H|T]) -> H + sum(T);
sum([]) -> 0.
Luego, se generará una excepción ya que la última cola no es la lista vacía, sino un átomo.