modo predefinito di eseguire codice in Haskell

Question

Nel codice seguente generalizzato:

nat = [1..xmax] 
xmax = *insert arbitrary Integral value here* 

setA = [2*x | x <- nat] 
setB = [3*x | x <- nat] 

setC = [4*x | x <- nat] 
setD = [5*x | x <- nat] 

setOne = setA `f` setB 
setTwo = setC `f` setD 

setAll = setOne ++ setTwo 

setAllSorted = quicksort setAll 

(si prega di notare che 'f' si distingue per una funzione di tipo

f :: Integral a => [a] -> [a] -> [a] 

che non è semplicemente ++)

in che modo Haskell gestisce il tentativo di stampare setAllSorted?

ottiene i valori per setA e setB, calcola setOne e quindi mantiene solo i valori per setOne in memoria (prima di calcolare tutto il resto)?

Oppure Haskell conserva tutto in memoria fino a quando non si ottiene il valore per setAllSorted?

Se quest'ultimo è il caso, come dovrei specificare (usando le funzioni main, do e tutte le altre cose di IO) che invece fa il primo?

Posso dire al programma in quale ordine calcolare e raccogliere i rifiuti? Se sì, come lo farei?

Answer 1

Il numero di setAllSorted è necessariamente inferiore o uguale a ogni elemento della coda. Pertanto, per determinare la testata, è necessario calcolare tutti i valori di setOne e setTwo. Inoltre, dal momento che tutti gli insiemi sono forme applicative costanti, credo che non saranno raccolti dopo averli calcolati. I numeri stessi saranno probabilmente condivisi tra i set, ma i nodi di contro che li incollano probabilmente non saranno (la tua fortuna con alcuni dipenderà dalla definizione di f).

Answer 2

A causa della pigrizia, Haskell valuta le cose su richiesta. Puoi pensare alla stampa fatta alla fine come "tirare" gli elementi dalla lista setAllSorted, e questo potrebbe tirarne fuori altre cose.

Cioè, l'esecuzione di questo codice è più o meno così:

1. stampa valuta prima il primo elemento di setAllSorted.
2. Poiché viene da una procedura di ordinamento, richiederà la valutazione di tutti gli elementi di setAll. (Poiché l'elemento più piccolo potrebbe essere l'ultimo).
3. La valutazione del primo elemento di setAll richiede la valutazione del primo elemento di setOne.
4. La valutazione del primo elemento di setOne dipende dall'implementazione di f. Potrebbe essere necessario valutare tutti o tutti i parametri setA e setB.
5. Dopo aver finito di stampare il primo elemento di setAllSorted, setAll sarà stato completamente valutato. Non ci sono più riferimenti a setOne, setTwo e ai set più piccoli, quindi tutti questi sono ormai idonei per la garbage collection. Il primo elemento di setAllSorted può anche essere recuperato.

Quindi, in teoria, questo codice non mancherà di tenere in memoria setAll maggior parte del tempo, mentre setAllSorted, setOne e setTwo sarà probabilmente occupare solo una quantità costante di spazio in qualsiasi momento.A seconda dell'implementazione di f, lo stesso può essere vero per i set più piccoli.