Leniwa potęga

Dla odmiany dzisiaj napiszę o Haskellu. Poznałem ten język stosunkowo niedawno (jakieś 1,5 roku temu) więc nie jestem żadnym ekspertem w temacie. Jednakże jedna rzecz nadzwyczaj mi się w nim spodobała i miałem nawet okazję ją ostatnio wykorzystać. Jest to jedna z wyróżniających cech tego języka czyli leniwa ewaluacja. Brzmi dość tajemniczo ale koncepcja jest bardzo prosta. Rozważmy prostą funkcję w C:

int check(int a, int b) {
    if (a > 100)
        return 100;
    if (a > b) 
        return b;

    return a;
}

Leniwa ewaluacja spowoduje, że jeżeli akurat zmienna a będzie większa niż 100 to zmienna b nie zostanie w ogóle wyliczona. Zauważmy, że pod zmienną b może kryć się szereg wywołań funkcji ciężkich obliczeniowo. Wówczas nasz program będzie działał znacznie szybciej w Haskellu niż w C (napisany w ten sposób).

Niestety jak ktoś kiedyś napisał, leniwa ewaluacja to nie święty graal programowania, to coś z czym trzeba nauczyć się żyć. Powoduje ona masę problemów związanych z przepełnieniem stosu. Chodzi o to, że żadna zmienna nie jest wyliczana od razu lecz dopiero w momencie gdy zostaje użyta. Zamiast jej wartości odkładany na stos jest adres do instrukcji, które pozwalają ją wyliczyć. Jeśli więc np. funkcja działa rekurencyjnie to może takich adresów sporo odłożyć i dochodzi wówczas do przepełnienia stosu.

Leniwa ewaluacja pozwala jeszcze na jedną rzecz. Mianowicie na definiowanie w programie typów nieskończonych oraz operacji na nich. W Haskellu zatem możliwe jest zapisanie listy wszystkich liczb naturalnych:

[0..] 

Odbywa się to w ten sam sposób jak powyżej. Dopóki nie żaden element z listy nie jest potrzebny to pamiętany jest tylko adres jak wyliczyć kolejny element listy. Oczywiście próba wypisania wszystkich elementów tej listy skończy się w końcu brakiem pamięci. Podam teraz przykład kiedy się to może przydać. Załóżmy, że mamy jakąś (skończoną) listę liczb i chcielibyśmy poznać najmniejszą liczbę naturalną, która nie należy do tej listy (ten problem występuje np. w zagadnieniach kolorowania grafu). W imperatywnym języku musielibyśmy pisać pętle z szeregiem instrukcji warunkowych, które strasznie zaciemniają istotę tego co robimy. Jak zatem wygląda to w Haskellu? A tak:

head $ [0..] // lista 

Te dwa ukośniki (//) to nie żaden komentarz tylko operator usuwający elementy z pierwszej listy (po lewej), które występują w drugiej (po prawej). Przeczytajmy więc to wyrażenie od lewej strony:

Weź pierwszy element (head) z listy powstałej z wyrażenia ($) różnicy (//) liczb naturalnych ([0..]) i listy (lista).

Wygląda to bardzo zwięźle i czytelnie a do tego nie musimy się martwić o warunki do sprawdzenia ani o zakres liczb do przeszukania. Podsumowując warto się zainteresować językami z leniwą ewaluacją lecz trzeba jej używać z głową :)