Warto być leniwym

08.12.2009 - Krzysztof Skrzętnicki
TrudnośćTrudnośćTrudność

Warto być leniwym... a przynajmniej czasami. W przypadku języka Haskell leniwy jest domyślny mechanizm przeprowadzania obliczeń: nie jest liczone nic, co nie jest niezbędnie potrzebne. Okazuje się, że daje nam to całą paletę ciekawych rozwiązań.

Leniwość, to znaczy "zrobię to później"

Jeżeli nie masz pojęcia o Haskellu kliknij tutaj

Dla zrozumienia artykułu potrzebna będzie pewna znajomość Haskella. Jako wstęp do programowania w tym języku można uznać ten artykuł. W niniejszym artykule wykorzystane będą pojęcia i funkcje tam wprowadzone.

O co więc dokładnie chodzi z tą leniwością? Zobaczmy na prostym przykładzie niewielkiego programu:

1
2
main = print (True || 
              error "Ta wartość jest niezdefiniowana!")

Po uruchomienu:

$ \$ $ runhaskell test1.hs 
True

Po uruchomieniu powyższy kawałek kodu wyświetli napis True. Operator || jest w języku Haskell leniwy ze względu na lewy argument: jeżeli lewy argument równy jest True, to wartość całego wyrażenia na pewno też będzie True. Z tego względu nie ma potrzeby zaglądać do drugiego argumentu. Zobaczmy, co by było, gdyby pierwszym argumentem stało się False, zamiast True.

1
2
main = print (False || 
              error "Ta wartość jest niezdefiniowana!")

$ \$ $ runhaskell test2.hs 
test2.hs: Ta wartość jest niezdefiniowana!

Dlaczego tak się dzieje? Zobaczmy na definicję ||.

1
2
True || _ = True
False || x = x

Widzimy więc, że zgodnie z tym czego oczekiwaliśmy, jeżeli pierwszym argumentem jest True, to drugi nie jest w żaden sposób ruszany. W przeciwnym wypadku drugi argument stanowi wynik obliczenia.

W razie problemów...

Leniwość w Haskellu potrafi czasem płatać różne figle. Dlatego aby móc śledzić przebieg obliczeń wymyślono szereg różnorodnych narzędzi. Do najprostszych z nich należy moduł Debug.Trace. Jest stosunkowo niewielki, bo eksportuje jedynie trzy funkcje. Nas interesować będzie jedna z nich, mianowicie trace. Ma ona następującą sygnaturę:

1
trace :: String -> a -> a

Funkcja trace opakowuje swoją wartość w specjalny sposób. Dzięki temu w momencie obliczenia tej wartości wyświetlony zostaje tekst przekazany jako pierwszy argument dla fukcji trace. Warto zwrócić uwagę na moment wyświetlenia tej wartości: dzieje się to dokładnie wtedy, gdy zarządamy wartości danego wyrażenia - czyli być może nigdy. Zobaczmy to ponownie na przykładzie operatora ||.

1
2
3
import Debug.Trace
main = print ((trace "obliczamy argument 1." True) || 
              (trace "obliczamy argument 2." False))

Po uruchomieniu:

$ \$ $ runhaskell test3.hs
obliczamy argument 1.
True

Po zamianie True na False:

1
2
3
import Debug.Trace
main = print ((trace "obliczamy argument 1." False) || 
              (trace "obliczamy argument 2." False)) 

Po uruchomieniu:

$ \$ $ runhaskell test4.hs
obliczamy argument 1.
obliczamy argument 2.
False

Leniwość popłaca

Zobaczmy więc przykład, gdzie leniwość pozwoli nam zmniejszyć ilość wykonywanej pracy, przy jednoczesnym zachowaniu elegancji kodu.

Chcemy napisać funkcję obliczającą pewne wartości statystyczne dla próbki liczb. Chcemy znać trzy parametry:

  1. Średnią
  2. Wariancję
  3. Odchylenie standardowe

Jeżeli nie wiesz co oznaczają poszczególne nazwy - nie przejmuj się, nie musisz! Ważne jest to, że do policzenia wariancji wykorzystywana jest średnia, a do obliczenia odchylenia standardowego - wariancja.

1
2
3
4
5
6
7
8
9
10
11
12
13
import Debug.Trace
policzStatystyki :: [Double] -> (Double,Double,Double)
policzStatystyki xs = 
 let suma = sum xs
     dlugosc = fromIntegral (length xs)
     -- średnia to suma wszystkich elementów podzielona przez ich liczbę
     srednia = trace "srednia" (suma / dlugosc)
     -- wariancja jest sumą (x - srednia)^2 dla wszystkich x z listy xs
     wariancja = trace "wariancja" (sum [ (x - srednia)^2 | x <- xs ])
     -- odchylenie standardowe to pierwiastek z wariancji
     odchylenieStd = trace "odchylenieStd" (sqrt wariancja)
 in
   (srednia, wariancja, odchylenieStd)


Dygresja na temat implementacji funkcji policzStatystyki
W implementacji funkcji policzStatystyki wystąpiło kilka prostych, lecz nowych elementów.
Po pierwsze pojawiło się kilka funkcji:
  1. sum - funkcja ta liczy sumę liczb na liście. Może sumować dowolne typy liczbowe, tak długo jak lista zawiera elementy tego samego typu.
  2. sqrt - zwykły pierwiastek kwadratowy. Nazwa funkcji jest skrótem od angielskiej nazwy square root, czyli właśnie pierwiastek kwadratowy.
  3. fromIntegral - funkcja przeprowadza konwersję z typu całkowitoliczbowego (integral) w inny typ liczbowy. W naszym przypadku potrzebujemy z typu Int (zwracanego przez funkcję length) otrzymać typ Double.
Kolejnym elementem jest słowo kluczowe let(co można przetłumaczyć na polskie "niech": niech x = 1 itd.). Pozwala ono na definiowanie symboli, które mogą być potem wykorzystane w kodzie. Przykładem zastosowania tego słowa kluczowego jest cała powyższa funkcja :-)
Ostatni element, czyli specjalna notacja dla list:
1
[ (x - srednia)^2 | x <- xs ]
wyjaśniony jest nieco dalej. Cierpliwości.

Zobaczmy jak działa nasza funkcja.

1
2
3
4
-- powyżej kod funkcji policzStatystyki
main = let (sr,war,odch) = policzStatystyki [1,2,3,4,5]
       in
         print (sr,war)

Po uruchomieniu zobaczymy:

$ \$ $ runhaskell test6.hs
srednia
wariancja
(3.0,10.0)

Zgodnie z oczekiwaniem nie została policzona wartość dla odchylenia standardowego. Niewielki zysk, gdyż obliczenie pojedynczego pierwiastka to niewielki koszt. Ale mogło być też inaczej:

1
2
3
4
-- powyżej kod funkcji policzStatystyki
main = let (sr,war,odch) = policzStatystyki [1,2,3,4,5]
       in
         print sr

Po uruchomieniu:

$ \$ $ runhaskell test7.hs
srednia
3.0

Jak widzimy, ponieważ nie wykorzystaliśmy wartości wariancji, nie została ona policzona wcale. A to już jest spory zysk! Jednocześnie zauważmy, że nie musieliśmy w żaden specjalny sposób modyfikować kodu. Język sam zadbał o to, by wyliczone zostały tylko te fragmenty, które są potrzebne.


Ćwiczenie
Przetestuj działanie funkcji policzStatystyki. Sprawdź, jak działa np. policzStatystyki [8,2,1]
Przykładowa odpowiedź:
policzStatystyki [5,1,8,2,1,2,3]

5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com