Come concatizzare gli elenchi in erlang senza creare elenchi annidati?

Question

Sto cercando di essere un buon erlanger ed evitare "++". Ho bisogno di aggiungere una tupla alla fine di un elenco senza creare un elenco annidato (e, si spera, senza doverlo ricostruire e invertire). Dato tuple T e le altre liste L0 e L1:

Quando uso [T | L0] ottengo [tuple, List0].

Ma quando io uso [L0 | T], ottengo lista annidata [[List0] | tuple]. Allo stesso modo, [L0 | L1] restituisce [[lista0] | lista1].

Rimozione delle parentesi elenco esterno L0 | [T] produce un errore di sintassi.

Perché "|" non simmetrico? C'è un modo per fare quello che voglio usando "|"?

Answer 1

| non è "simmetrico" perché una lista non vuota ha una testa e una coda dove la testa è un singolo oggetto e la coda è un altro elenco. Nell'espressione [foo | bar]foo denota il capo della lista e bar è la coda. Se la coda non è un elenco corretto, anche il risultato non sarà un elenco corretto. Se la testa è una lista, il risultato sarà semplicemente una lista con quell'elenco come primo elemento.

Non esiste un modo per aggiungere alla fine di un elenco collegato in meno di O (n). Questo è il motivo per cui l'uso di ++ viene generalmente evitato. Se ci fosse una sintassi speciale da aggiungere alla fine dell'elenco, sarebbe comunque necessario impiegare O (n) per il tempo e usare quella sintassi non ti renderà più un "buon erlanger" rispetto all'utilizzo di ++.

Se si desidera evitare il costo O (n) per inserimento, è necessario anteporre e quindi annullare. Se sei disposto a pagare il costo, potresti anche usare ++.

Un po 'più in dettaglio su come liste di lavoro:

[ x | y ] qualcosa chiamato una cella cons. In termini C è fondamentalmente una struttura con due membri. Un elenco corretto è la lista vuota ([]) o una cella contro il cui secondo membro è un elenco appropriato (nel qual caso il primo membro viene chiamato head e il secondo membro è chiamato tail).

Pertanto, quando si scrive [1, 2, 3], vengono create le seguenti celle: [1 | [2 | [3 | []]]]. Cioè la lista è rappresentata come una cella contro il cui primo membro (la sua testa) è 1 e il secondo membro (la coda) è un'altra cella. Quella altra cellula di contro ha 2 come la sua testa e ancora un'altra cella come la sua coda. Quella cella ha 3 come la sua testa e la lista vuota come la sua coda.

Il movimento di un elenco di questo tipo viene effettuato in modo ricorsivo eseguendo prima la parte iniziale dell'elenco e quindi chiamando la funzione di attraversamento sulla coda dell'elenco.

Ora se si desidera anteporre un elemento a tale elenco, questo è molto semplice: basta creare un'altra cella di controllo la cui testa è il nuovo oggetto e la cui coda è la vecchia lista.

L'aggiunta di un elemento tuttavia è molto più costosa perché la creazione di una cella singola cella non è sufficiente.Devi creare una lista uguale a quella vecchia, eccetto che la coda dell'ultima cella di controllo deve essere una nuova cella contro la cui testa è il nuovo elemento e la cui coda è la lista vuota. Quindi non puoi aggiungere una lista senza passare per l'intera lista, che è O (n).