¿Cómo concat listas en erlang sin crear listas anidadas?

Question

Estoy tratando de ser un buen erlanger y evitar "++". Necesito agregar una tupla al final de una lista sin crear una lista anidada (y con suerte sin tener que construirla hacia atrás y revertirla). Dada tupla T y las listas de L0 y L1:

Cuando uso [T | L0] me sale [tupla, List0].

Pero cuando se utiliza [L0 | T], consigo lista anidada [[List0] | tupla]. Del mismo modo, [L0 | L1] devuelve [[list0] | list1].

Eliminando los corchetes de la lista externa L0 | [T] produce un error de sintaxis.

¿Por qué es "|" no simétrico? ¿Hay alguna manera de hacer lo que quiero usando "|"?

Answer 1

| no es "simétrica" ​​porque una lista no vacía tiene una cabeza y una cola donde la cabeza es un solo elemento y la cola es otra lista. En la expresión [foo | bar]foo denota el encabezado de la lista y bar es la cola. Si la cola no es una lista adecuada, el resultado tampoco será una lista adecuada. Si el encabezado es una lista, el resultado será simplemente una lista con esa lista como primer elemento.

No hay forma de anexar al final de una lista vinculada en menos de O (n) tiempo. Esta es la razón por la cual generalmente se rechaza el uso de ++. Si hubiera una sintaxis especial para agregar al final de la lista, aún necesitaría tomar O (n) tiempo y usar esa sintaxis no lo haría más "bueno" que usar ++.

Si desea evitar el costo de O (n) por inserción, deberá preceder y luego retroceder. Si está dispuesto a pagar el costo, puede usar ++.

Un poco más de detalle sobre cómo funcionan las listas:

[ x | y ] algo que se llama una célula contras. En términos C, es básicamente una estructura con dos miembros. Una lista adecuada es la lista vacía ([]) o una celda de cons cuyo segundo miembro es una lista adecuada (en cuyo caso el primer miembro recibe el nombre de cabeza y el segundo miembro se denomina cola).

Así que cuando escribe [1, 2, 3] esto crea las siguientes celdas cons: [1 | [2 | [3 | []]]]. Es decir. la lista se representa como una celda de cons cuyo primer miembro (su cabeza) es 1 y el segundo miembro (la cola) es otra celda de cons. Esa otra célula de cons tiene 2 como su cabeza y otra célula cons como su cola. Esa celda tiene 3 como cabeza y la lista vacía como cola.

El desplazamiento de dicha lista se realiza recursivamente actuando primero en el encabezado de la lista y luego llamando a la función transversal en la cola de la lista.

Ahora, si quiere anteponer un elemento a esa lista, esto es muy fácil: simplemente crea otra celda de cons cuyo encabezado es el nuevo elemento y cuya cola es la lista anterior.

Sin embargo, agregar un artículo es mucho más costoso porque la creación de una única celda de cons no es suficiente.Debe crear una lista que sea la misma que la anterior, excepto que la cola de la última celda de cons debe ser una nueva celda de cons cuyo encabezado sea el elemento nuevo y cuya cola sea la lista vacía. Entonces no puedes agregar a una lista sin revisar toda la lista, que es O (n).