C'è qualche ragione particolare per l'uso di liste su code nei linguaggi di programmazione funzionale?

Question

C'è qualche ragione particolare per l'uso di liste su code nei linguaggi di programmazione funzionale?

#1 da (16 voti)
#2 da (2 voti)

5

La maggior parte dei linguaggi di programmazione funzionale come Scheme e Haskell utilizzano gli elenchi come struttura dati principale. Le code sono identiche alle liste, ad eccezione del fatto che l'aggiunta alla fine, non all'inizio, ha un tempo costante. Ogni algoritmo che viene scritto elegantemente usando liste con head e tail può essere scritto elegantemente usando le code con init e last .

Considerare l'accodamento fino alla fine è più comune del contrario, direi che le code sono più naturali delle liste. C'è qualche ragione per cui le liste sono sempre state preferite?

scheme functional-programming data-structures haskell

posta MaiaVictor 25.12.2013 - 20:45

fonte

2 risposte

Leggi altre domande sui tag scheme functional-programming data-structures haskell

Quanto è significativa la complessità temporale di Big-O di un algoritmo? Controllo della dimensione dell'array in C / C ++ per evitare errori di segmentazione

score 16 · Answer 1

Le code non compongono in modo funzionale e sono difficili da implementare in modo efficiente senza renderle modificabili.

La natura stessa di una coda suggerisce che ci metti delle cose e ne prendi le cose, il che è in contrasto con la natura immutabile dei linguaggi funzionali. Oh, certo, puoi fare la stessa cosa con le liste, ma in generale quello che stai facendo è comporre una nuova lista, non aggiungerne una, e una lista non ha il requisito speciale di obbligarti a mettere gli oggetti in una sola estremità e portali fuori dall'altra, come fa una coda.

Tutto ciò che ho detto, dai un'occhiata al documento su strutture di dati puramente funzionali di Okasaki che delinea una strategia per creare una coda con prestazioni adeguate in modo funzionale.

score 2 · Answer 2

Queues are identical to lists, except for the fact appending to the end - not to the begin - has constant time.

Le code sono comunemente intese come FIFO strutture, che sono non "identico agli elenchi oltre all'aggiunta fino alla fine". Con le code, di solito scrivi alla coda e leggi dalla testa; questa è una semantica completamente diversa.

Se intendi una struttura LIFO , allora stai davvero parlando di uno stack, che è il modo in cui le Liste sono più comunemente usate nel codice ricorsivo / funzionale. In tal caso, perché ti interessa che chiamiamo la posizione da cui leggiamo e scriviamo alla testa o alla coda? Il modo di lavorare con esso sarebbe lo stesso in entrambi i casi. L'unico contesto in cui farebbe la differenza è dove l'elenco viene usato anche come stringa (una preoccupazione piuttosto banale).

Gli elenchi / stack sono strutture molto utili nella programmazione funzionale:

La testa può rappresentare lo stato di un calcolo.
La struttura è persistente , riducendo al minimo la copia e preservando l'immutabilità.
testa e coda accesso in tempo costante con una struttura molto più semplice di qualsiasi tipo indicizzato (codice sottostante più semplice ecc.)

Le code perdono alcuni di questi benefici (ad es. persistenza) e aggiungono complessità a nessun guadagno. Se il vantaggio principale è che trovi le code più facili da capire, prova più difficile.