Programowanie funkcjonalne - inne spojrzenie na świat

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

Obywatele świata funkcji

Funkcja zipWithM wprowadziła bardzo ważny koncept: funkcje mogą być traktowane jako zwykłe wartości i przekazywane do innych funkcji. Otwiera to całą gamę nowych możliwości. Jakie nowe użyteczne funkcje operujące na listach możemy teraz napisać?

map - czyli dla każdego po równo!

Często zdarza się, że chcemy wyliczyć funkcji zaaplikowanej dla każdego z elementów listy. Na przykład chcemy pomnożyć każdy z elementów listy przez 3. Spróbujmy najpierw napisać kod który realizuje to zadanie wprost.

Każdy element listy musimy zastąpić nowym, trzykrotnie większym. Jeżeli lista jest pusta, zwracamy pustą listę.

1
2
3
kazdyRazy3 [] = [] -- lista pusta, zwracamy pustą
kazdyRazy3 (x:xs) = (x*3) : kazdyRazy3 xs -- głowę mnożymy razy 3, na ogonie
                                          -- wywołujemy rekurencyjnie funkcję

Nasza funkcja składa się z jakby dwóch części. Pierwsza odpowiada za ogólny kształt tego, jak działa funkcja: uruchamia pewną operację dla każdego z elementów listy wejściowej. Druga część to to, jaka operacja jest wykonywana: w naszym przypadku mnożenie przez 3.

Możemy więc rozłączyć te dwie części. Chcemy uzyskać funkcję, która zachowuje pierwszą część, zaś druga powinna być "ruchoma". Wystarczy więc, że operację mnożenia zastąpimy wywołaniem funkcji f przekazywanej jako parametr. Tak dochodzimy do definicji funkcji map:

1
2
map _ [] = []
map f (x:xs) = f x : map f xs

Widzimy, że nasza nowa funkcja jest bardzo podobna w budowie do funkcji kazdyRazy3. Doszedł jedynie nowy parametr, który wykorzystujemy w tworzeniu nowych wartości.


Wpisz kod poniżej, aby go uruchomić. Sprawdź jak działa np.

1
map (3*) [1,2,3]

albo

1
map (++[5]) [[2],[8],[4]]
. Zgadnij wynik obliczenia:

1
map razyTrzy [[2],[4],[6]]


Pana tu nie chcemy

Jedną z cech funkcji map jest to, że zachowuje ona liczbę elementów na liście. Czasami jednak chcielibyśmy usunąć pewne elementy z wyniku.

Napiszmy więc funkcję zostawiającą na liście tylko elementy parzyste. Następnie przekształcimy ją w funkcję bardziej ogólną.

1
2
3
4
5
jestParzysta = even -- even to po angielsku 'parzysta'
tylkoParzyste [] = [] -- dla listy pustej zwracamy listę pustą
tylkoParzyste (x:xs) = if jestParzysta x 
 then x : tylkoParzyste xs -- parzyste zostają
 else     tylkoParzyste xs -- pomijamy nieparzyste

Jak działa ta funkcja? Dla listy pustej zwracamy listę pustą. Jeżeli element jest nieparzysty, to pomijamy go. W przeciwnym wypadku dołączamy go do wyniku.

Funkcja filter jest podobna do naszej funkcji tylkoParzyste: przechodzi całą listę i usuwa z niej pewne elementy, pozostałe zostawiając bez zmian. Funkcja ta pobiera jednak jeszcze jeden dodatkowy argument: funkcję która mówi o tym, czy usunąć element, czy też go zostawić.

W jaki sposób uogólnić tylkoParzyste by otrzymać filter? Okazuje się to bardzo proste. Zauważmy, że użyliśmy w implementacji tylkoParzyste funkcję jestParzysta. Możemy teraz zapomnieć o tej funkcji i zamiast niej dodać nowy parametr funkcji - funkcję decydującą o losie elementu.

1
2
3
4
filter _ [] = []
filter f (x:xs) = if f x 
then x : filter f xs
else     filter f xs

Zrobiliśmy teraz coś bardzo podobnego jak w przypadku funkcji map: najpierw napisaliśmy pewną szczególną funkcję, którą potem uogólniliśmy do bardziej uniwersalnej funkcji.

Co właściwie zyskujemy dzięki funkcjom typu map czy filter? Przede wszystkim oszczędzamy wysiłek i czas: nie musimy pisać stu różnych funkcji do modyfikowania list. Wystarczy że podamy odpowiedni parametr. Oto przykładowe zastosowania funkcji filter.

  1. Wybranie tylko parzystych i tylko nieparzystych elementów z listy. W pierwszym przypadku pierwszym parametrem jest funkcja even, w drugim - złożenie funkcji even z funkcją not (kilka słów o funkcji not).

  2. W języku Haskell nie ma operatora zaprzeczenia tak jak np. w języku C, gdzie operatorem tym jest wykrzyknik !. Zamiast tego istnieje funkcja not, o definicji takiej jak poniżej:
    1
    2
    
    not True = False
    not False = True
    Dzięki temu, że zaprzeczenie jest zwykłą funkcją, możemy ją składać z innymi funkcjami, np. z funkcją even.
    1
    2
    
    filter even [1,2,3,4,5] -- [2,4]
    filter (not . even) [1,2,3,4,5] -- [1,3,5]
  3. Zostawienie elementów tylko powyżej 12 lub poniżej 10.
  4. 1
    2
    
    filter (>12) [4,14,20,2,20,1,20,12,14,9] -- [14,20,20,20,14]
    filter (<10) [4,14,20,2,20,1,20,12,14,9] -- [4,2,1,9]

    Samo zastosowanie funkcji filter nie wymaga komentarza. Pytania mogą się zrodzić w odniesieniu do operatora <. W Haskellu podobnie jak wiele innych operatorów jest to funkcja dwuargumentowa. Możemy więc podać jej jeden z argumentów, zostawiając jeszcze miejsce na drugi. Jest to tak zwana częściowa aplikacja i działa również dla innych funkcji.


    Wpisz kod poniżej, aby go uruchomić. Potestuj funkcję filter!


3.5
Twoja ocena: Brak Ocena: 3.5 (6 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com