Perché è '(cons 1 (cons 2 (cons 3 nil)))' e non '(cons 3 (cons 2 (cons 1 nil))) per [1,2,3]?

Naviga le tue risposte
5

C'è qualche motivo speciale per costruire una lista in Scheme che usi 

(cons 1 (cons 2 (cons 3 nil)))

invece di 

(cons 3 (cons 2 (cons 1 nil)))

? Mentre il primo sembra più ovvio perché legge nell'ordine corretto, il secondo è quello che riduce nell'ordine corretto. Inoltre, sembra più naturale costruire una lista partendo da zero e aggiungendo elementi ad essa, non il contrario. Ho anche scoperto che quest'ultimo ha proprietà come essere molto amichevole al curry: (cons 1) diventa piacevolmente a function that appends 1 to a list .

    
posta MaiaVictor 25.12.2013 - 23:17
fonte

4 risposte

13

Come proponi di raggiungere la testa in questa lista rovesciata? Se non si utilizzano strutture mutabili, l'elenco invertito sarebbe performante solo se si eseguisse il tempo lineare della testa e la coda costante. Ma ora hai esattamente la stessa struttura di prima, tranne che stai chiamando la testa alla coda e viceversa.

la struttura è così com'è, indipendentemente da quale parte si dichiari il fronte o il retro, quella particolare forma è l'unica nota con readahead costante di tempo e inserimento di tempo costante senza mutazione o esecuzione di trucchi di ammortamento.

ti stai appiccando ai termini pensando che un lato potrebbe essere la testa o la coda, ma quei termini non contano, la parte che conta è la struttura.

    
risposta data 26.12.2013 - 07:32
fonte
3

Perché l'accodamento alla fine di un elenco collegato è O (n) e l'accodamento in primo piano è O (1). L'operazione che stai cercando si chiama snoc e può essere implementata. Ma in modo inefficiente.

Per capire perché, renditi conto che quando aggiungi un elenco alla parte posteriore, se non muti nulla, ogni singolo elemento deve essere copiato, dove come con l'aggiunta in primo piano, puoi semplicemente allocare una cella di controllo e fare riferimento all'elenco esistente, un'operazione relativamente economica.

    
risposta data 25.12.2013 - 23:45
fonte
3

Come ho menzionato in un commento nella tua domanda precedente, se vuoi elenchi concatenati immutabili, un'implementazione semplice usando le celle cons può avere solo o un puntatore () successivo o successivo em> un puntatore indietro (precedente), non entrambi. In altre parole, sono elenchi collegati singolarmente.

Ciò significa che se vuoi rappresentare (1 2 3) usando (cons 3 (cons 2 (cons 1 '()))) , la tua variabile punta al nodo "ultimo" (contenente il 3), e attraversi "all'indietro" per arrivare al 2, quindi 1. Utilizzando questo sistema, sarebbe impossibile accedere al nodo 2 dal nodo 1, quindi non è possibile attraversare facilmente l'elenco nell'ordine (1 2 3) .

    
risposta data 25.12.2013 - 23:47
fonte
0

Usiamo il primo metodo perché produce l'elenco corretto. Il secondo produce una lista inversa. Il nil mostra molto chiaramente quale elemento deve essere l'ultimo.

L'ordine conta!

Guarda questo semplice esempio in Common Lisp: 

(reduce #'expt (cons 1 (cons 2 (cons 3 nil))))
1
(reduce #'expt (cons 3 (cons 2 (cons 1 nil))))
9

Potresti utilizzare il secondo metodo se hai l'implementazione della lingua per gestire l'ordine inverso sotto il cofano, ma poi:

  1. l'implementazione sarebbe più complicata (= più opportunità per i bug)
  2. le prestazioni sarebbero influenzate come menzionato in altre risposte (alcuni casi, come gli attraversamenti completi, potrebbero avere il risultato della performance attenuato usando più memoria, cioè creando una copia dell'elenco nella direzione corretta dietro le quinte, quindi facendo il lavoro su quella copia. Sta facendo ancora due attraversamenti in cui solo uno sarebbe stato sufficiente prima.)
  3. gli umani inaffidabili dovrebbero ricordare di costruire le loro liste al contrario.
risposta data 05.07.2016 - 18:53
fonte

Leggi altre domande sui tag

Come utilizzare i principi SOLID in questo esempio È questo il modo corretto di includere questo software con licenza MIT nel mio software?