Obliczanie pracy wykonanej przez x = f (x, x)

Question

powiedzmy mam tej funkcji: (Haskell składni)

f x = (x,x) 

Jaka jest praca (ilość obliczeń) przeprowadzone przez funkcję?

Początkowo myślałem, że jest to oczywiście stałe, ale co jeśli typ x nie jest skończony, co oznacza, że ​​x może zająć dowolną ilość pamięci? Trzeba by wziąć pod uwagę pracę wykonaną przez skopiowanie x również, prawda?

To doprowadziło mnie do przekonania, że ​​praca wykonana przez funkcję jest w rzeczywistości liniowa w rozmiarze wejścia.

To nie jest praca domowa dla siebie, ale pojawił się, gdy miałem do określenia pracy wykonywanej przez funkcję:

f x = [x] 

który ma podobny problem, jak sądzę.

Answer 1

Bardzo nieformalna praca zależy od semantyki operacyjnej języka. Haskell, dobrze, to leniwy, więc płacisz tylko stałe czynniki:

• pchania wskaźniki do x na stosie
• przeznaczyć komórkę sterty dla (,)
• zastosować (,) do swoich argumentów
• zwróci wskaźnik do komórki sterty

Zrobione. O (1) praca, wykonywana, gdy dzwoniący patrzy na wynik f.

Teraz można wywołać dalszą ocenę jeśli spojrzeć wewnątrz (,) - i że praca jest uzależniona od pracy w celu oceny x się. Ponieważ w Haskell są udostępniane odniesienia do x, oceniasz je tylko raz.

Tak więc praca w Haskell to O (praca x), jeśli w pełni ocenisz wynik. Twoja funkcja f dodaje tylko stałe czynniki.

Answer 2

Chris Okasaki ma cudowną metodę określania pracy związanej z wywołaniem funkcji, gdy wprowadzane jest (lub całkowite) lenistwo. Uważam, że jest to w jego pracy na temat czysto funkcjonalnych struktur danych. Wiem, że jest w wersji książkowej - przeczytałem tę część książki w zeszłym miesiącu. Zasadniczo naliczasz stały czynnik za obietnicę/thunk stworzony, nie naliczasz nic za ocenę jakichkolwiek przekazanych obietnic/porwań (zakładając, że zostały już wymuszone/są w normalnej formie [nie tylko WHNF]). To niedoszacowanie. Jeśli chcesz przecenić opłatę również koszt wymuszenia/konwersji do normalnej formy każdej obietnicy/thunk stworzony przez funkcję. Przynajmniej tak to pamiętam w moim skrajnie zmęczonym stanie.

Zobacz w Okasaki: http://www.westpoint.edu/eecs/SitePages/Chris%20Okasaki.aspx#thesis - Przysięgam, że wykorzystana teza będzie dostępna do pobrania.