Costruire un elenco sequenziale in lingue con cons / linked lists

Question

Costruire un elenco sequenziale in lingue con cons / linked lists

#1 da (4 voti)
#2 da (0 voti)

1

Nelle lingue in cui gli elenchi di cons sono un tipo di dati principale, è molto semplice creare un elenco dall'ultimo al primo antepreggendo gli elementi. Quando si esegue l'elaborazione da un file di input, tuttavia, è più probabile che si incontrino gli articoli in ordine di primo all'ultimo.

In genere, le lingue come queste sono recettive?

(define (parse file)
  ...
  (cons datum (parse file)))

Utilizzare le operazioni di aggiunta ad ogni passaggio? Costruisci la lista in ordine inverso e poi invertirla?

Esiste qualche schema di progettazione canonica che può risolvere il problema che l'input è in genere in ordine inverso rispetto al modo in cui viene costruita la lista?

design-patterns list linked-list

posta John Cartwright 04.07.2013 - 07:41

fonte

2 risposte

0

Sì, i linguaggi che favoriscono i tipi di dati ricorsivi quasi sempre favoriscono anche le funzioni ricorsive, e per questo tipo di elaborazione dei flussi è la soluzione più ovvia. (In particolare se il linguaggio runtime supporta l'eliminazione della ricorsione di coda, cosa che di solito fa.) Con l'elaborazione ricorsiva, la lista in effetti viene fuori nell'ordine corretto, quindi tutto va bene.

L'aggiunta è spesso comparabilmente costosa e renderebbe un problema lineare efficace in uno quadratico, quindi di solito è un anti-modello nei linguaggi di programmazione funzionale.

risposta data 04.07.2013 - 08:41

fonte

Leggi altre domande sui tag design-patterns list linked-list

Esistono server SQL che supportano le query compilate? Una semplice attribuzione soddisfa i requisiti della licenza BSD per il riutilizzo o è necessario copiare l'intera nota sul copyright?

score 4 · Accepted Answer

Un modo comune per farlo in modo efficiente, almeno in Haskell, sta usando una lista di differenze che consente O (1 ) snoc , che è l'inverso di cons (sì, è un nome sciocco).

Un'alternativa non è l'uso di liste collegate a favore di una struttura dati più appropriata, come le barrette ( Data.Seq in Haskell, tempo costante ammortizzato cons / snoc ) o le code (ci sono code persistenti con costante operazioni temporali, sia ammortizzate che peggiori).