ghc trasforma un elenco usato una sola volta in un generatore per motivi di efficienza?

Question

In tal caso, si tratta di una parte dell'ottimizzazione standard o specifica per ghc su cui possiamo fare affidamento? O solo un'ottimizzazione di cui non possiamo necessariamente dipendere.

P.S .: Quando ho provato un campione di prova, sembrava indicare che stava avvenendo/

Prelude> let isOdd x = x `mod` 2 == 1 
Prelude> let isEven x = x `mod` 2 == 0 
Prelude> ((filter isOdd).(filter isEven)) [1..] 

mastica CPU, ma non consuma molta memoria.

Answer 1

Dipende da cosa intendi per generatore. L'elenco viene generato pigramente e, poiché nient'altro lo fa riferimento, le parti consumate vengono raccolte automaticamente quasi immediatamente. Poiché il risultato del calcolo sopra non aumenta, l'intero calcolo viene eseguito in uno spazio costante. Questo non è richiesto dallo standard, ma poiché è più difficile implementare una semantica non-strittiva con un comportamento spaziale diverso per quell'esempio (e molto vagamente simile), in pratica si può fare affidamento su di esso.

Ma normalmente, l'elenco viene comunque generato come elenco, quindi sono presenti molti rifiuti. In circostanze favorevoli, ghc elimina l'elenco [1 .. ] e produce un ciclo non ripartisce:

result :: [Int] 
result = filter odd . filter even $ [1 .. ] 

(utilizzando le funzioni Prelude pigrizia), compilati con -O2 genera il nucleo

List.result_go = 
    \ (x_ayH :: GHC.Prim.Int#) -> 
    case GHC.Prim.remInt# x_ayH 2 of _ { 
     __DEFAULT -> 
     case x_ayH of wild_Xa { 
      __DEFAULT -> List.result_go (GHC.Prim.+# wild_Xa 1); 
      9223372036854775807 -> GHC.Types.[] @ GHC.Types.Int 
     }; 
     0 -> 
     case x_ayH of wild_Xa { 
      __DEFAULT -> List.result_go (GHC.Prim.+# wild_Xa 1); 
      9223372036854775807 -> GHC.Types.[] @ GHC.Types.Int 
     } 
    } 

Un ciclo normale , in esecuzione da 1 a maxBound :: Int, non producendo nulla sulla strada e [] alla fine. È quasi abbastanza intelligente da restituire semplicemente []. Nota che c'è solo una divisione per 2, GHC sa che se uno Int è pari, non può essere dispari, così che il controllo è stato eliminato, e in nessun ramo viene creata una lista non vuota (cioè, i rami non raggiungibili hanno stato eliminato dal compilatore).

Answer 2

Strettamente parlando, Haskell non specifica alcun particolare modello di valutazione, quindi le implementazioni sono libere di implementare la semantica del linguaggio come vogliono. Tuttavia, in qualsiasi implementazione sana, incluso GHC, puoi fare affidamento su questa esecuzione in uno spazio costante.

In GHC, i calcoli come questi si traducono in un elenco collegato singolarmente che termina in un thunk che rappresenta il resto dell'elenco che non è stato ancora valutato. Mentre valuti questo elenco, più della lista sarà generata su richiesta, ma poiché l'inizio della lista non è riferito a nessun'altra parte, le parti precedenti sono immediatamente idonee per la garbage collection, quindi ottieni un comportamento spaziale costante.

Con le ottimizzazioni attivate, è molto probabile che GHC esegua la deforestazione, ottimizzando la necessità di avere un elenco, e il risultato sarà un semplice ciclo senza allocazione eseguita.