Warto być leniwym

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

List comprehensions

W poprzednim akapicie po cichu przemyciłem pewien zapis, który powinien wydać się znajomy dla wszystkich, którzy mieli do czynienia z matematyką. Chodzi mianowicie o zwięzłą notację dla list, zwaną po angielsku list comprehension.

1
2
3
-- z kodu funkcji policzStatystyki:
      -- wariancja jest sumą (x - srednia)^2 dla wszystkich x z listy xs
      wariancja = trace "wariancja" (sum [ (x - srednia)^2 | x <- xs ])

List comprehension stanowi zapis:

1
[ (x - srednia)^2 | x <- xs ]

Zapis ten rozumiemy dość intuicyjnie: jest to lista elementów równych (x-srednia)^2, dla każdego x należącego do listy xs. Zapis ten przypomina matematyczną notację dla zbiorów:

$$ \{ (x-srednia)^2 \| x \in xs \} $$

W odróżnieniu od notacji matematycznej w przypadku Haskella efektem nie jest zbiór lecz lista elementów, które na dodatek występują w określonej kolejności.


Ćwiczenie (list comprehension)
Korzystając z notacji dla list napisz wyrażenie, które odpowiada liście sześcianów (^3) liczb [1,9,12,612,62123]
Przykładowa odpowiedź:
1
2
[ x^3 | x <- [1,9,12,612,62123] ]
    

Od jeden do nieskończoności...

Jest jeszcze jeden sposób zastosowania notacji dla list. Możemy za jej pomocą definiować różnorakie ciągi. Przykładowo:

1
2
3
liczbyNaturalne, liczbyParzyste :: [Integer]
liczbyNaturalne = [1..] -- 1,2,3,4,5 ... 
liczbyParzyste = [0,2..] -- 0,2,4,6,8,10 ... 

Uważny czytelnik może zastanawiać się, ile elementów zawierają obie te listy. Poprawna odpowiedź brzmi: nieskończenie wiele.

Odpowiedź ta może być szokująca dla osób, które w swoim życiu zetknęły się jedynie z językami, które nie mają mechanizmu leniwości (mówi się o nich, że są to języki gorliwe). Haskell jest jednak językiem leniwym! Jeżeli napiszemy program, który wykorzysta tylko określoną liczbę (np. 1000) elementów z danej listy, to nie potrzebujemy znać wartości pozostałych. Nasz program więc zakończy się w skończonym czasie pomimo tego, że operujemy w nim strukturami nieskończonymi! Zobaczmy to na przykładzie.

1
2
3
4
main = let naturalne = [1..] :: [Integer]
           parzyste = [0,2..] :: [Integer]
       in
         print (take 10 (zip naturalne parzyste))

Po uruchomieniu:

$ \$ $ runhaskell test8.hs 
[(1,0),(2,2),(3,4),(4,6),(5,8),(6,10),(7,12),(8,14),(9,16),(10,18)]

Obliczonych zostało dokładnie 10 elementów z każdej listy - i nie więcej.


Parę słów o funkcjach zip i take
Funkcja zip była już omawiana wcześniej. Przypomnijmy jednak krótko, jak działa.
zip operuje na dwóch listach. Jej zadaniem jest "spięcie" obydwu list w jedną listę par. Elementów na liście wyjściowej będzie dokładnie tyle ile wynosi długość krótszej z obu list. Elementy parowane są od początku list i odrzucane są takie, które nie posiadają pary. Implementacja funkcji zip wygląda następująco:
1
2
zip (x:xs) (y:ys) = (x,y) : zip xs ys -- jeżeli obie listy są niepuste zwracamy parę głów
zip _ _ = [] -- w przeciwnym wypadku zwracamy listę pustą
Przykładowo możemy uruchomić funkcję zip na napisie (który jest listą znaków) i liście liczb naturalnych:
1
2
zip "abrakadabra" [1..]
[('a',1),('b',2),('r',3),('a',4),('k',5),('a',6),('d',7),('a',8),('b',9),('r',10),('a',11)]
Funkcja take jest jeszcze prostsza. Zwraca ona pierwszych n elementów listy, do której jest ona zaaplikowana. Przykład zastosowania:
1
(take 2 "Haskell") ++ "!"
Jako wynik zobaczymy:
1
"Ha!"
Implementacja tej funkcji jest łatwa:
1
2
take 0 xs = []
take n (x:xs) = x : take (n-1) xs

Ćwiczenie (list comp. + take)
Napisz z pomocą notacji listowej listę wszystkich liczb nieparzystych. Wybierz z niej następnie pierwszych 100 elementów za pomocą funkcji take.
Przykładowa odpowiedź:
take 100 [1,3..]

Uwaga na pułapki

Trzeba jednak wiedzieć, że leniwa ewaluacja bywa niebezpieczna. Możemy bardzo prosto napisać program, który nigdy się nie kończy. Wystarczy, że spróbujemy wyliczyć np. długość nieskończonej listy. Potrzebna nam wtedy będzie ona cała. Program potrzebować więc będzie nieskończonego czasu. Równie dobrze możemy poprosić o ostatni element nieskończonej listy albo o odwróconą listę nieskończoną.

Każdy z poniższych programów nigdy nie zakończy się z sukcesem.

1
2
3
4
main1 = print (last ([1..] :: [Integer]))
main2 = print (reverse ([1..] :: [Integer]))
main3 = print (length ([1..] :: [Integer]))
main4 = print (sum ([1..] :: [Integer]))

Co gorsza, nie tylko nie zakończą się one nigdy, ale potrafią także zużyć nieskończone zasoby pamięci! Dzieje się tak dla main2, main3 i main4. Wyjątkowo wyraźnie możemy to zobaczyć dla main2. Uruchomiony kod bardzo szybko wyczerpie wszelką dostępną pamięć: aby zwrócić swój wynik tworzy w pamięci nieskończoną listę. Nie zaczyna jej jednak wypisywać, ponieważ brakuje mu pierwszego elementu do wypisania, a jest nim ostatni element listy nieskończonej.

Wniosek: leniwość, choć przydatna, potrafi być niebezpieczna!

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com