Prestazioni di concatenazione di elenchi seguita da scansione

4

Considera il seguente frammento di codice:

-- list_1 = [1, 2, 3]
-- list_2 = [4, 5, 6] 
final_list =  list_1 ++ list_2
result = map (+1) final_list

Il tempo impiegato da esso è proporzionale solo alla lunghezza di final_list e il prezzo della concatenazione di liste non viene pagato?

La mia idea è che la concatenazione avvenga pigramente; per citare la fonte di GHC Base.hs,

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

Poiché map elimina costantemente la testa della lista, suppongo che la concatenazione fatta dalla chiamata ricorsiva nell'ultima riga sia sempre eseguita in un blocco con l'esecuzione di map , quindi list_1 viene effettivamente scansionato solo una volta.

È corretto?

    
posta 9000 26.08.2015 - 20:08
fonte

1 risposta

3

È corretto. È facile testare la tua teoria rendendo list_2 infinito:

list_1 = [1, 2, 3]
list_2 = repeat 4
final_list = list_1 ++ list_2
result = map (+1) final_list

print $ take 10 result
-- Outputs [2,3,4,5,5,5,5,5,5,5]

Congratulazioni! Hai appena fatto un ciclo infinito in pochi microsecondi! (Non proprio).

    
risposta data 27.08.2015 - 00:35
fonte

Leggi altre domande sui tag