Kanał ATOM
Autor wpisu: Piotr Śliwa, dodany: 05.11.2015 23:19, tagi: php
Ostatnio można było odnieść wrażenie, że tak jak tytuł mówi, jestem leniwy (ostatni wpis na początku roku), ale nic bardziej mylnego. Już zabieram się za temat leniwej ewaluacji. Wyjdę od Scali, a później przejdę do PHP.
Leniwa ewaluacja na przykładzie Scali
Są dwa sposoby ewaluacji wyrażeń: chciwe (strict) oraz leniwe (lazy). Scala jest językiem, który domyślnie wyrażenia ewaluuje chciwie (tak jak większość języków), ale gdy tego chcemy, możemy oznaczyć aby dane wyrażenie było leniwe.
lazy val a = 1 + 2
lazy val b = a + 3
val c = a + b // obliczenie wartości a i b odbywa się dopiero tutaj
// a nie w momencie inicjalizacji zmiennej
Listy i większość innych kolekcji w scali są chciwe, jedną z leniwych struktur jest Stream - jest to leniwa wersja listy. Przykład strumienia będącego nieskończonym ciągiem liczb naturalnych:
val naturals: Stream[Int] = 0 #:: naturals.map(_ + 1)
//res0: Stream[Int] = Stream(0, ?)
Powyższy zapis jest skróconym zapisem:
val naturals: Stream[Int] = Stream.cons(0, naturals.map(_ + 1))
Poniżej dwa akapity wyjaśnień, bo mimo iż zapis ten jest prosty, naturalny i dosyć matematyczny, mózg może się przed nim lekko opierać.
Co to jest rekurencyjna struktura danych? Wyjaśnię to na przykładzie. Matrioszka to klasyczna rosyjska zabawka składająca się z X lalek. X - 1 lalek jest otwieranych i może zawierać w sobie kolejną (mniejszą) lalkę. Ostatnia lalka nie jest otwierana i nie można już do niej nic wsadzić. Tak więc pierwsza lalka zawiera drugą, która zawiera trzecią i tak do ostatniej, która nie zawiera już kolejnej lalki. Każda z lalek ma ten sam "interfejs", wygląda podobnie. Ostatnia lalka różni się od reszty tym, że nie zawiera kolejnej. Podobnie jest ze strukturami rekurencyjnymi. W przypadku strumieni, "lalkę" mogąca zawierać inną "lalkę" nazywamy Cons, zaś ostatnią pustą "lalkę" Empty. Cons jest węzłem, który ma wartość i referencję do pozostałej części strumienia (ogona). Empty to pusty strumień. Konstruktor Cons wygląda następująco: Cons(value, Stream) - ma referencję do przechowywanej wartości oraz dalszej części strumienia. Dalsza część strumienia może być Cons lub Empty (otwierana lub ostatnia pusta "lalka"). Przykładowy strumień złożony z 2 elementów: Stream.cons(0, Stream.cons(1, Stream.Empty)) lub składnia skrócona: 0 #:: 1. Jako referencji do całego strumienia używamy referencję do jego pierwszego elementu - tak samo jak w przypadku matrioszki, pierwsza lalka jest lalką samą w sobie, nie jest potrzebne dodatkowe opakowanie tak jak w przypadku klasycznej listy powiązanej.
Wracając do naszego ciągu liczb naturalnych (ignorujemy to że może się przekręcić po dojściu do max int). 0 to pierwszy element strumienia, naturals.map(_ + 1) to strumień będący dalszą częścią głównego strumienia (drugim argumentem konstruktora Cons). Bardzo ważne jest to, że naturals.map(_ + 1) jest ewaluowane leniwie, czyli wartość drugiego elementu zostanie wyliczona tylko gdy będziemy chcieli go odczytać. Zapis może na początku lekko kołować, ale wystarczy sobie uświadomić, że jest to rekurencyjna definicja równoznaczna z rekurencyjnym wywołaniem funkcji:
def createNaturals(from: Int): Stream[Int] = from #:: createNaturals(from+1)
val naturals = createNaturals(0)
Jeśli dwa poprzednie akapity nie są jasne, przeczytaj je jeszcze raz (rekurencyjnie, aż do spełnienia warunku wyjścia) ;)
Wyliczenie wartości następuje tylko gdy chcemy tą wartość odczytać:
naturals(5) //pobranie 5-tego elementu ciągu
//następuje ewaluacja ciągu do 5-tego
//elementu włącznie, 6-ty element nie jest ewaluowany
//res1: Int = 5
Ok, teraz trochę bardziej złożony przykład - definicja ciągu fibonacciego:
