Haskell: Lista fuzji, gdzie jest to potrzebne?

Question

Powiedzmy mamy następujące:

l = map f (map g [1..100]) 

I chcemy zrobić:

head l 

więc otrzymujemy:

head (map f (map g [1..100])) 

Teraz musimy zdobyć pierwszy element to. map definiuje coś tak:

map f l = f (head l) : (map f (tail l)) 

Tak więc otrzymujemy:

f (head (map g [1..100])) 

A potem znowu zastosowano:

f (g (head [1..100])) 

co skutkuje

f (g 1) 

Nie pośredni li stsy powstają, po prostu z powodu lenistwa.

Czy ta analiza jest prawidłowa? I prostych struktur tak:

foldl' ... $ map f1 $ map f2 $ createlist 

są wykazy pośredniczących kiedykolwiek stworzone, nawet bez „listy fusion”? (Myślę, że lenistwo powinno je wyeliminować trywialnie).

---

Jedynym miejscem widzę powodu, by utrzymywać wykaz jest, jeśli zrobiliśmy:

l' = [1..100] 
l = map f (map g l') 

Gdzie możemy chcesz zachować l', jeśli stosuje się go w innym miejscu. Jednak w powyższym przykładzie powinno być dość trywialne, aby kompilator szybciej je zrealizował, aby ponownie przeliczyć powyższą listę, niż ją zapisać.

Answer 1

W przykładzie map komórki listy są tworzone, a następnie natychmiast zbierane śmieci. W przypadku fuzji listy nie jest wymagana żadna manipulacja GC ani thunk (które nie są wolne).

Answer 2

Fuzja przynosi najwięcej korzyści, gdy pośrednie struktury danych są drogie. Kiedy przekazywana struktura jest leniwy i dostępna w sposób sekwencyjny, struktury mogą być względnie tanie (jak ma to miejsce w przypadku list).

• Dla leniwych struktur, fuzja usuwa stały czynnik tworzenia thunk i natychmiastowo zbiera śmieci.
• W przypadku struktur ścisłych fuzja może usunąć pracę O (n).

Największe korzyści wynikają z zastosowania sztywnych tablic i podobnych struktur. Jednak nawet łączenie leniwych list jest wciąż wygraną, ze względu na większą lokację danych, ponieważ mniej struktur pośrednich jest przydzielanych jako pakiety.