Programowanie funkcjonalne - inne spojrzenie na świat

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

Złożenia funkcji

Jedną z kluczowych cech programowania funkcjonalnego jest możliwość składania funkcji ze sobą - dzięki czemu z prostych elementów możemy tworzyć dowolnie skomplikowane algorytmy.

Złożenie funkcji oznaczane jest podobnie jak w matematyce kropką, np.

1
fZlozona = sum . razyTrzy

Identyczny jak w matematyce jest też kierunek składania. Funkcja fZlozona pomnoży więc najpierw element pierwszy przez trzy (funkcja razyTrzy), a następnie wyliczy sumę wszystkich elementów na liście (funkcja sum).

Dla konkretnych danych wygląda to tak:

1
fZlozona [1,2,3] = sum (razyTrzy [1,2,3]) = sum [3,2,3] = 8

Kilka ćwiczeń
  1. Spróbuj wpisać jakiś argument dla funkcji fZlozona i obserwuj rezultaty.
  2. Zgadnij, jaką wartość musi mieć xs, by:
  3. 1
    2
    3
    
    fZlozna xs = 22
    fZlozona (razyTrzy xs) = 28
    fZlozona (1 : xs) = 23
  4. Napisz funkcję fZlozona2, tak by zachodziła równość:
  5. 1
    
    fZlozona2 y (x:xs) = (y*3 : y : x*3 : xs)

    Użyj tylko żłożeń funkcji poznanych już wcześniej. Twój kod powinien trafić w miejsce kropek:

    fZlozona2 y xs = ...

Dalej w las

Spróbujmy teraz zaimplementować kilka popularnych funkcji operujących na listach. Będziemy je nazywać ich oryginalnymi, angielskimi nazwami - przy okazji możemy podszkolić swój angielski :-)

Pierwsze z nich to head, tail, null - czyli po polsku głowa, ogon, pusty. Kolejnymi będą init, last - początek, koniec.

Funkcja head zwraca głowę, tail - ogon listy, zaś null sprawdza, czy lista jest pusta. Implementacja tych funkcji jest bardzo prosta - prostsza niż funkcji które pisaliśmy w poprzednim akapicie.

1
2
3
4
head (x:_) = x
tail (_:xs) = xs
null [] = True
null _ = False

W porównaniu z tym, co widzieliśmy wcześniej, nie są to skomplikowane funkcje - każda z nich używa znanych nam już konstrukcji.


Wpisz kod poniżej, aby go uruchomić. Potestuj, jak działają funkcję tail, null. Dla jakiego argumentu tail zwróci błąd?

Uwaga: dla tego argumentu trzeba w sposób jawny nadać mu typ za pomocą ::, np. tak: tail (xs :: [Int]).


Zajmijmy się teraz funkcjami init i last. Funkcje te uzupełniają się wzajemnie: pierwsza z nich zwraca wszystkie elementy, za wyjątkiem ostatniego, zaś druga zwraca dokładnie ostatni element.

Funkcje te są nieco bardziej skomplikowane - aby obliczyć swoją wartość potrzebują wywołać same siebie w sposób rekurencyjny. Zacznijmy od funkcji last.

1
2
3
4
last [] = error "Lista pusta nie ma ostatniego elementu"
last [x] = x -- ostatni element listy jednoelementowej to jej pierwszy element
last (_:xs) = last xs -- wywołanie rekurencyjne: ostatnim elementem listy
                      -- jest ostatni element jej ogona

Pierwszy przypadek rozpatruje listę pustą - w tym przypadku zwracamy błąd. Ostatnim elementem listy jednoelementowej jest oczywiście jej głowa - jedyny element. W przypadku zaś, gdy lista nie jest jednoelementowa, zadziała ostatnia linijka: ostatnim elementem listy, która jest dłuższa od jednoelementowej, jest ostatni element jej ogona. Stąd wywołanie last xs.

Funckja init jest podobna.

1
2
3
4
init [] = error "Lista pusta nie ma niepustego początku"
init [x] = [] -- ignorujemy ostatni element listy
-- "x" nie jest ostatnim elementem listy, więc umieszczamy go w wyniku
init (x:xs) = x : init xs 

Chcemy wyliczyć listę pozbawioną ostatniego elementu. Lista pusta nie ma czegoś takiego jak "ostatni element" - stąd dla listy pustej zwracamy błąd. Pozbawiona ostatniego elementu lista jednoelementowa to lista pusta - o tym mówi nam linijka druga. Ostatnia linijka z kolei mówi nam by nie usuwać elementu, który nie jest ostatni.


Wpisz kod poniżej, aby go uruchomić. Potestuj nowo poznane funkcje!


Dygresja o typach

Zdarza się, że chcemy wyrazić w języku programowania zdanie takie jak "zmienna X jest typu Int" albo "wartość Z jest typu Q". Tego typu wyrażenia są częścią Haskella. Zapisuje się je za pomocą operatora czterokropka :: (czyli inaczej podwójnego dwukropka :-)

Mamy tu typy proste takie jak liczby całkowite (Int), zmiennoprzecinkowe (Float) czy znaki (Char). Informacje o typie zapisujemy tak, jak w tym przykładzie:

1
2
3
1 :: Int
3.141 :: Float
'a' :: Char

Jaki więc typ mają używane przez nas wcześniej listy? Ogólny typ listy jest następujący:

1
pewnaLista :: [a]

Czym jest to tajemnicze a występujące w typie listy? Otóż podobnie jak funkcje mają swoje argumenty, tak samo i typy mogą mieć swoje zmienne. Parametr a nazywany jest zmienną typową i może przybierać dowolne wartości. Dla listy liczb całkowitych mamy:

1
[1,2,3,4] :: [Int]

Czyli w tym przypadku a to tyle co Int. A jaki typ mają napisy, których użyliśmy na samym początku artykułu? Okazuje się, że to również są listy, tyle że znaków:

1
"jeden, dwa, trzy" :: [Char] -- tutaj zmienna typowa 'a' przybiera wartość Char

Zauważmy jednak, że gdy zmienna typowa a przyjmie już swoją wartość, nie zmienia jej w obrębie danego wyrażenia. Jeżeli jeden element listy ma typ Int, to muszą go mieć także wszystkie pozostałe. Nie możemy więc umieścić na jednej liście znaków i liczb. Poniższy przykład nie skompiluje się!

1
lista = [1,'b'] -- błąd: 1 to liczba, natomiast 'b' to znak


Wpisz kod poniżej, aby go uruchomić. Sprawdź co się stanie po wpisaniu [1,2,3] :: [Int], a co po wpisaniu [1,2,3] :: [Double].


Nieco więcej o strukturach danych

Poznaliśmy już jedną ze struktur danych Haskella - listy. Listy pozwalają na przechowywanie dowolnej liczby elementów. Inna struktura, która zawiera zawsze taką samą liczbę elementów, to krotka (mniej przyjazna nazwa: n-tka uporządkowana). Oto przykłady:
1
2
3
4
5
6
-- krotka 4-elementowa. To nie to samo co ['b','a','c','a'] !
('b','a','c','a') :: (Char,Char,Char,Char) 
(1,2,3) :: (Int,Int,Int) -- krotka 3-elementowa
(3.141,0) :: (Float,Int) -- krotka 2-elementowa, czyli para.
-- w Haskellu nie ma krotek jednoelementowych
() :: () -- krotka zeroelementowa, zwana z angielskiego "unit"

Krotki przydają się, gdy chcemy grupować razem kilka elementów, być może różnego typu. Przykładem może być np. lista zakupów:

1
zakupy = [("mleko",3.5),("czekolada",2.5),("kawa",15.8)]

Każdy z elementów to para (nazwa produktu, cena). Moglibyśmy zapisać tą samą listę w postaci dwóch niezależny list:

1
2
nazwyProduktow = ["mleko","czekolada","kawa"]
cenyProduktow = [3.5, 2.5, 15.8]

Ale wtedy mogłoby się okazać, że listy nie zgadzają się co do długości! Jak zinterpretować takie dwie listy:

1
2
nazwyProduktow = ["kaktus","mleko","czekolada","kawa"]
cenyProduktow = [3.5, 2.5, 15.8]

nazwyProduktow ma długość o 1 większą niż cenyProduktow. Dla zmiennej zakupy nie było takiego problemu. Widzimy teraz, że używając par (a w ogólności krotek) możemy zapewnić, że jednych elementów będzie dokładnie tyle samo co drugich.


Napisz testowo kilka różnych krotek. Postaraj się określić dla każdej jej typ. Jaki jest typ krotki (1,'a') ?


Zamki błyskawiczne, czyli zipping

Wyobraźmy sobie teraz sytuację następującą: mamy dwie listy elementów, i chcemy połączyć je w pary. Jak to zrobić?

Okazuje się, że jest to zadanie dość powszechne - i istnieje funkcja realizująca to zadanie. Zwyczajowo nazywa się ona zip: podobnie jak zamek błyskawiczny spina dwie części w jedną, tak samo funkcja ta paruje razem elementy.

Spróbujmy zdefiniować zachowanie funkcji zip.

1
2
3
4
5
--jeżeli którakolwiek z list wejściowych jest pusta, zwróc listę pustą
zip _ [] = []
zip [] _ = []
-- w przeciwnym wypadku weź głowę z każdej listy, zwróć parę i rekurencyjnie wywołaj zip
zip (x:xs) (y:ys) = (x,y) : zip xs ys

Z pewnych powodów, o których nie będę tutaj mówić, funkcja zip dostępna w standardowej bibliotece języka Haskell jest zdefiniowana dokładnie tak, jak powyżej. W przypadku gdy którakolwiek lista wejściowa jest pusta, zwracamy listę pustą. Gdy obie są niepuste, zwracamy (ponownie rekurencyjnie):

  1. parę głów list: (x,y)
  2. połączone funkcją zip ogony list: zip xs ys

Od szczegółu do ogółu

Możemy teraz wyobrazić sobie inną, bardziej ogólną funkcję. Co by było w przypadku, gdybyśmy chcieli w podobny sposób zsumować odpowiednie elementy w parach? Albo wymnożyć? Czy musielibyśmy od nowa pisać cały kod programu?

W językach funkcjonalnych tego typu zadania realizuje się poprzez przekazywanie funkcji jako parametrów innych funkcji. Zobaczmy jak to działa!

Zmodyfikujemy kod funkcji zip: jako pierwszy, dodatkowy parametr pobierać będzie funkcję spinającą dwa elementy w pewien sposób. Użyjemy jej by uzyskać zamierzony efekt.

1
2
3
4
5
zipWith _ _ [] = []
zipWith _ [] _ = []
-- w przeciwnym wypadku weź głowę z każdej listy, zaaplikuj funkcję f 
-- i rekurencyjnie wywołaj zipWith
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys

Funkcja działa podobnie do funkcji zip, ale zamiast zwracać parę liczb wykonuje na nich jakąś operację. Nie jest istotne jaka to jest operacja, jeżeli zwracamy listę pustą (a tak jest w dwóch pierwszych linijkach - dlatego zamiast f mamy tam _). Jeżeli zwracamy jakiś element, to aplikujemy do niego naszą funkcję.

Możemy w ten sposób wykonać te wszystkie rzeczy, które zamierzyliśmy. Zobaczmy to na przykładzie sumowania:

1
2
3
4
5
zipWith (+) [1,2,3] [4,5,6] = 
(1+4) : zipWith (+) [2,3] [5,6] = 
(1+4) : (2+5) : zipWith (+) [3] [6] = 
(1+4) : (2+5) : (3+6) : [] = 
[5,7,9]

Co istotne - nie musimy definiować żadnych nowych funkcji: wystarczy zipWith i odpowiednia funkcja pomocnicza (tak - w Haskellu plus "+" to funkcja!). W podobny sposób można wykorzystać zipWith do wykonania wielu użytecznych operacji.


Wypróbuj działanie funkcji zip i zipWith. Zgadnij, jaki będzie wynik obliczenia:

1
zipWith (&&) [True,True,False,True] [False,True,True,False]

Sprawdź, czy Twoje przypuszczenia były słuszne.


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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com