Se ho un puro linguaggio di programmazione funzionale con * ottimizzazione molto molto intelligente * proccess, è possibile ragionare sull'utilizzo della memoria, semplicemente guardando la firma del tipo?
add :: Int -> [Int] -> [Int]
F. E. Se la risposta alla mia domanda fosse sì, la funzione add assegnerebbe esattamente (1 + n + y) * sizeof (Int).
Il motivo per cui ho posto la domanda qui è che faccio fatica a trovare un contro esempio.
No, il blocco del problema colpisce ancora:
fn add(n: Int, ns: [Int]) -> [Int] {
if halts(add) {
loop {}
}
return ns.map(|v| {v+n})
}
A seconda che add si fermi o meno, allocherà O(length(ns)) di memoria o nessuna memoria.
Qualcosa da tenere a mente è che il tipo di ritorno di una funzione non garantisce che la funzione restituirà qualcosa di quel tipo .
Una firma di tipo fornisce la garanzia molto più debole che la funzione non restituirà qualcosa che non è di quel tipo. In particolare, consente di non restituire nulla, come un loop infinito o un'interruzione dell'alimentazione (anche se un'interruzione dell'alimentazione potrebbe non essere considerata pura) e l'escape fuori banda, come le eccezioni.
No. Prendere in considerazione:
tailn :: Int -> [Int] -> [Int]
che è la funzione che prende l'ennesima coda del suo secondo input (o errore se questo non esiste). Questo non ha bisogno di allocare memoria in quanto le code sono tutte condivise
Potresti essere in grado di richiedere questo per funzioni in cui esiste una sola implementazione possibile per la firma data (es. id), ma solo se si escludono anche le implementazioni patologiche (ad esempio un'implementazione di id con una perdita).
Per un esempio non patologico del tuo caso originale che utilizza più memoria:
flatReplicate :: int -> [Int] -> [Int]
flatReplicate n ns = concat (replicate n ns)
che ripete il suo secondo argomento n volte e lo appiattisce in una singola lista; questo dovrebbe essere O (n ^ 2) caso peggiore.
Non è nemmeno possibile dire cosa farà la funzione da quel tipo di firma, per non parlare di quanta memoria ci vuole. Ecco alcune possibili implementazioni valide di quel tipo di firma:
add n ns = [0] -- memory O(1), time O(1)
add n ns = ns -- memory O(length(ns)), time O(1)
add n ns = repeat n -- memory infinite, time infinite (assuming strictness)
Un esempio meno patologico senza liste infinite e senza semplicemente ignorare (uno di) gli argomenti:
add n ns = (take (n*n) $ repeat n) ++ ns
-- memory O(n^2 + length(ns)), time … too tired to think about :-D
Leggi altre domande sui tag functional-programming memory-usage