Domyślny sposób wykonywania kodu w Haskell

Question

W poniższym kodzie uogólnionej:

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 

(należy pamiętać, że „f” oznacza funkcję typu

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

że nie jest to po prostu ++)

W jaki sposób uchwyt Haskell próbuje wydrukować zestawAllSortowane?

czy otrzyma wartości dla setA i setB, obliczyć setOne, a następnie zachować tylko wartości setOne w pamięci (przed obliczeniem wszystkiego innego)?

Czy Haskell zachowuje wszystko w pamięci, dopóki nie uzyska wartości dla setAllSorted?

Jeśli to drugie ma miejsce, to jak określiłbym (używając funkcji main, do i wszystkich innych rzeczy IO), czy zamiast tego robi to pierwsze?

Czy mogę powiedzieć programowi, w jakiej kolejności obliczyć i zebrać śmieci? Jeśli tak, to jak mam to zrobić?

Answer 1

Głowa setAllSorted jest koniecznie mniejsza niż lub równa każdemu elementowi w ogonie. W związku z tym w celu określenia głowy należy obliczyć wszystkie wartości: setOne i setTwo. Ponadto, ponieważ wszystkie zestawy są stałymi formami aplikacyjnymi, uważam, że nie zostaną zebrane podczas wyliczania. Same numery będą najprawdopodobniej współdzielone między zestawami, ale węzły, które je sklejają, prawdopodobnie nie będą (twoje szczęście z niektórymi będzie zależeć od definicji f).

Answer 2

Z powodu lenistwa Haskell ocenia rzeczy na żądanie. Możesz pomyśleć, że drukowanie na końcu jest "ciągnięciem" elementów z listy setAllSorted i może pociągnąć za sobą inne rzeczy.

Oznacza to, że działa ten kod to idzie mniej więcej tak:

1. Druk ocenia najpierw pierwszy element setAllSorted.
2. Ponieważ jest to wynikiem procedury sortowania, będzie wymagało oceny wszystkich elementów setAll. (Ponieważ najmniejszy element może być ostatnim).
3. Ocena pierwszego elementu setAll wymaga oceny pierwszego elementu z setOne.
4. Ocena pierwszego elementu setOne zależy od sposobu implementacji f. Może to wymagać oceny całości lub żadnej z wartości setA i setB.
5. Po zakończeniu drukowania pierwszy element z setAllSorted, setAll zostanie w pełni oceniony. Nie ma już odwołań do setOne, setTwo i mniejszych zestawów, więc wszystkie z nich mogą teraz zostać usunięte. Pierwszy element setAllSorted może również zostać odzyskany.

Więc teoretycznie, kod ten będzie utrzymywać setAll w pamięci przez większość czasu, a setAllSorted, setOne i setTwo będzie prawdopodobnie tylko zajmują stałą ilość miejsca w dowolnym czasie.W zależności od implementacji f to samo może dotyczyć mniejszych zestawów.