Perché questo codice non è spazio costante?

Question

Attualmente sto imparando Haskell (essendo un programmatore di mestiere, ma questo è il mio primo tentativo di linguaggio funzionale).

Desidero scrivere una funzione che analizza una lista e restituisce sia l'elemento minimo che massimo di tale elenco. Una sorta di cosa fanno le funzioni Preludio minimum e maximum, ma entrambe allo stesso tempo. Mi è venuta in mente il seguente codice:

import Data.List 

-- Declaration of rand 

minMax :: [Int] -> Maybe (Int, Int) 
minMax [] = Nothing 
minMax (x:xs) = Just (foldl' f (x, x) xs) 
       where 
        f (a, b) c = (if c < a then c else a, if c > b then c else b) 

rand è una funzione che genera una lista infinita di numeri. Il fatto è che quando ho aggiungere il main seguente funzione:

main = print $ minMax $ take 1000000 $ rand 7666532 

compilare ed eseguire tutto questo con profiling, mi mostra che utilizza più di 200 MB di memoria, quindi non è sicuramente una funzione costante dello spazio (che Mi piacerebbe che fosse).

La domanda è perché e cosa dovrei cambiare per risolverlo. Come ho capito, lo foldl' piega l'elenco da sinistra (allo stesso modo in cui viene generato) e non è pigro, quindi non vedo perché l'utilizzo della memoria sia così elevato. Sono abbastanza sicuro che sia la funzione minMax che non è corretto, in quanto è sufficiente stampare il suddetto elenco, utilizzando

main = print $ take 1000000 $ rand 7666532 

mi dà l'utilizzo di 1 MB, una cosa che ho capito e si aspettano.

Answer 1

Si noti che foldl' obbliga l'accumulatore a debole modulo testa normale. Poiché l'accumulatore è una tupla, lo non è forzare la valutazione dei due elementi della tupla.

Se si forza esplicitamente i due elementi si ottiene una funzione costante-space:

f (a, b) c = a `seq` b `seq` (if c < a then c else a, if c > b then c else b) 

Nel programma originale si stanno costruendo una tupla del tipo: (<thunk>, <thunk>) e ogni volta f viene applicato semplicemente costruire una tupla con thunk sempre più grandi. Quando finalmente questo viene consumato da print la chiamata a show impone la valutazione completa della tupla e tutti i confronti sono fatti in quel punto.

Utilizzando seq è invece necessario forzare f per valutare il confronto in quel momento, quindi i thunk contenuti nell'accumulatore vengono valutati prima di eseguire il confronto. Quindi il risultato è che i thunk memorizzati nell'accumulatore hanno dimensioni costanti.

Ciò che foldl' fa è semplicemente evitare di costruire il thunk: f (f (f ...) y) x.

Una soluzione alternativa, come suggerito da Jubobs, per evitare in modo esplicito utilizzando seq è quello di utilizzare un tipo di dati che ha campi severe:

data Pair a b = Pair !a !b 
    deriving Show 

E così il codice sarebbe diventato:

minMax :: [Int] -> Maybe (Pair Int Int) 
minMax [] = Nothing 
minMax (x:xs) = Just (foldl' f (Pair x x) xs) 
       where 
        f (Pair a b) c = Pair (if c < a then c else a) (if c > b then c else b) 

Questo evita completamente i thunk.

Answer 2

La funzione seq utilizzata in foldl' forza essenzialmente la valutazione del suo primo argomento fino a WHNF (Debole testa normale).

Come spiegato here, la valutazione WHNF si interrompe una volta l'applicazione di un costruttore . (a, b) è quindi sempre in WHNF, anche se a e sono thunk dal momento che si sta colpendo il costruttore Tuple prima di arrivare a a e b.

Come risultato, questo spazio perdite nonostante l'uso di foldl':

foldl' (\ (a, b) x -> (a + x, b + x)) (0, 1) [1..1000000] 

ma questo non:

foldl' (\ (a, b) x -> a `seq` b `seq` (a + x, b + x)) (0, 1) [1..10000000] 

È anche talvolta conveniente utilizzare l'estensione -XBangPatterns scrivere questo:

foldl' (\ (!a, !b) x -> (a + x, b + x)) (0, 1) [1..10000000]