Paradygmaty programowania/Wykład 11: Programowanie funkcyjne w Haskellu II

From Studia Informatyczne


Spis treści

Wstęp

Nasz Czytelnik zapewne już dawno zauważył, że w programowaniu funkcyjnym rekurencja odgrywa olbrzymią rolę. Uściślijmy tę obserwację — właściwie chodzi o trójcę: rekurencyjne funkcje, rekurencyjne typy danych i dowody indukcyjne. Przykłady rekurencyjnych definicji funkcji już omawialiśmy, dowody indukcyjne każdy widział w szkole, więc zacznijmy od przedstawienia przykładu rekurencyjnego typu danych.


Definiowanie rekurencyjnego typu danych

Otóż klasyczny przykład to liczby naturalne. Pierwsza rzecz to zdefiniowanie, co to jest; napiszmy:

 data Nat = Zero | Nast Nat

Definicja ta mówi Haskellowi, że elementem typu Nat jest Zero oraz rezultat zastosowania funkcji Nast do dowolnego elementu typu Nat. Zauważmy, że wcale nie specyfikujemy, co to jest Zero ani co to jest Nast. Tworu „Zero” nie musimy definiować — on po prostu oznacza siebie, czyli identyfikator Zero. Równie dobrze moglibyśmy użyć innego, nie mylącego się z niczym napisu. Znaczenie funkcji Nast określimy pośrednio, gdy za jej pomocą zdefiniujemy operacje na typie Nat, np. dodawanie i mnożenie. Na razie wiadomo tylko tyle, że typem Nast jest Nat -> Nat. Notabene, Nast jest nie tyle funkcją, co konstruktorem typu. Uwaga techniczna: identyfikatory oznaczające typy, klasy typów lub konstruktory typów muszą zaczynać się od dużej litery, natomiast identyfikatory oznaczające zmienne (także typowe) — od małej.

Na razie nie ma też żadnego związku między elementami typu Nast a znanymi nam reprezentacjami liczb naturalnych, np. reprezentacją dziesiętną. Taki związek można stworzyć, deklarując Nat jako typ należący do klasy Show i definiując sposoby reprezentacji jego elementów. Dla klasy standardowej — a taką jest Show — można też wykorzystać mechanizm dziedziczenia; wówczas stworzona zostanie automatycznie metoda reprezentowania elementów z typu Nat (niezbyt ciekawa). Mechanizm ów uruchamia się klauzulą deriving:

 data Nat = Zero | Nast Nat
   deriving Show

Jeśli jednak chcielibyśmy wyświetlać elementy typu Nat w reprezentacji dziesiętnej, możemy np. zdefiniować funkcję, która „przetłumaczy” je na liczby całkowite, a następnie zgłosić typ Nat jako instancję klasy Show, z odpowiednią definicją metody show:

 data Nat = Zero | Nast Nat
 
 nat2int :: Nat -> Integer
 nat2int Zero = 0
 nat2int (Nast x) = 1 + nat2int x
 
 instance Show Nat where
   show x = show (nat2int x)

Pora na definicję dodawania, rzecz jasna rekurencyjną:

 dodNat :: (Nat, Nat) -> Nat
 dodNat (x, Zero) = x
 dodNat (x, Nast y) = Nast (dodNat (x, y))

Jeśli dodatkowo chcemy mieć operator dodawania w bardziej klasycznej postaci, możemy napisać:

 (#) :: Nat -> Nat -> Nat
 (#) = curry dodNat

Oczywiście można od razu napisać definicję operatora w postaci rozwiniętej.

Inne działania, np. mnożenie, definiuje się analogicznie do dodawania:

 mnóżNat :: (Nat, Nat) -> Nat
 mnóżNat (x, Zero) = Zero
 mnóżNat (x, Nast y) = dodNat(y, mnóżNat (x, y))

Podobnie jak przydatne jest zadeklarowanie typu Nat jako instancji klasy Show, rozsądne wydaje się zgłoszenie go jako instancji klasy Eq, wraz z implementacją relacji równości:

 instance Eq Nat where
   Zero == Zero      = True
   Nast x == Zero    = False
   Zero == Nast x    = False
   Nast x == Nast y  = (x == y)

Zauważmy, że jest to — jak zwykle — definicja rekurencyjna, wykorzystująca przy tym dopasowywanie do wzorca. Inne klasy, dla których typ Nat mógłby być instancją, to Integral i Ord. Trzeba wówczas oczywiście zdefiniować wymagane dla tych klas metody, np. operatory <, <=, > i >= dla Ord oraz div i mod dla Integral.

Przytoczone przykłady pokazują, że w Haskellu można zbudować typ danych „od zera” (dosłownie i w przenośni...). Choć rekurencyjne definicje arytmetyki są nie najlepsze pod względem efektywności, stanowią na pewno dobrą ilustrację elastyczności języka funkcyjnego.

Do czego może się przydać indukcja?

Wyobraźmy sobie, że nie wiemy, jak zdefiniować odejmowanie dla typu Nat, ale znamy jego własności, powiedzmy:

 (x + y) – y = x

Spróbujmy poprowadzić dowód indukcyjny względem y. Dla y = Zero mamy:

 (x + Zero) – Zero = x – Zero

Żeby zatem uzyskać wymaganą równość, trzeba przyjąć x – Zero = x. W kroku indukcyjnym liczymy:

 (x + Nast y) – Nast y = x
 Nast (x + y) – Nast y = x
 Nast (x + y) – Nast y = (x + y) – y

Podstawiając x = x + y i przyjmując Nast x – Nast y = x – y, otrzymujemy żądaną równość. Tym samym stworzyliśmy definicję odejmowania:

 x – Zero = x
 Nast x – Nast y = x – y

Przy odrobinie szczęścia metody tej można użyć do stworzenia całkiem przydatnych (a nieoczywistych) definicji rekurencyjnych.

Ogólna postać definicji rekurencyjnych

Dla wielu jednoargumentowych funkcji typu Nat -> Nat możemy wyróżnić prosty schemat ich definicji rekurencyjnych. Wygląda on tak:

 f :: Nat -> Nat
 f Zero = c
 f (Nast x) = h (f x)

Innymi słowy, wartości f na kolejnych elementach typu Nat to kolejne iteraty funkcji h na stałej c. Pamiętając o odpowiedniości typu Nat z liczbami 0, 1, 2, ..., możemy napisać (w istocie używamy liczb całkowitych do zliczania aplikacji Nast):

 f :: Nat -> Nat
 f x = iter(nat2int x, h) c

Przykładowo, mnożenie przez dwa (Nast (Nast Zero)) możemy opisać jako:

 mn2 :: Nat -> Nat
 mn2 x = iter(nat2int x, (# Nast (Nast Zero))) Zero

Tutaj stała c to Zero, a funkcja h to (# Nast (Nast Zero)), czyli zdefiniowany przez nas wcześniej operator # z ustalonym jednym argumentem.

Uogólnijmy postać definicji rekurencyjnych jeszcze bardziej. Po pierwsze, typ wyniku definiowanej funkcji może być dowolny — nazwijmy go T. Po drugie, całość można zapisać jako aplikację specjalnej funkcji (nazwijmy ją rekdef) na funkcji h i stałej c. Tutaj funkcja h jest typu T -> T, a stała c — po prostu T, więc ogólna definicja rekdef używa nieograniczonej zmiennej typowej:

 rekdef :: (a -> a) -> a -> Nat -> a
 rekdef h c Zero = c
 rekdef h c (Nast x) = h (rekdef h c x)

Mnożenie przez dwa można teraz wyrazić jako:

 mn2 = rekdef (# Nast (Nast Zero)) Zero

Zauważmy teraz, że identyczną technikę można zastosować do standardowych liczb całkowitych (wykorzystując tylko ich „naturalną połowę”); zmodyfikujmy funkcję rekdef:

 rekdef :: (a -> a) -> a -> Integer -> a
 rekdef h c 0 = c
 rekdef h c (x + 1) = h (rekdef h c x)

Rozważmy definicję:

 f :: Integer -> (Integer, Integer)
 f = rekdef g (0, 1)
   where g (x, y) = (y, x + y)

Jest to funkcja, która wylicza dwa kolejne wyrazy ciągu Fibonacciego bez fatalnej wykładniczej rekurencji... Wystarczy więc wziąć pierwszy element tej pary, by uzyskać efektywną funkcję liczącą z dawna upragniony wyraz ciągu:

 fib :: Integer -> Integer
 fib = fst . rekdef g (0, 1)
   where g (x, y) = (y, x + y)

Do tej — bardzo funkcyjnej — techniki będziemy wracali w kontekście funkcji działających na listach. Dodajmy, że oprócz funkcji rekdef występuje tu charakterystyczna technika „łączenia w pary”, którą można zastosować z pominięciem rekdef:

 fibS :: Integer -> (Integer, Integer)
 fibS 0 = (0, 1)
 fibS (n + 1) = (y, x + y)
   where (x, y) = fibS n
 
 fib :: Integer -> Integer
 fib = fst . fibS

Listy

Dla języka funkcyjnego, w którym rekurencja odgrywa zasadniczą rolę, listy są strukturą bardzo naturalną. Elastyczność, z jaką język funkcyjny pozwala działać na listach, jest trudna do osiągnięcia w „zwykłych” językach.


Konstruowanie list

Przypomnijmy: listy zapisuje się w Haskellu jako ciąg elementów w nawiasach kwadratowych, rozdzielonych przecinkami. Wszystkie elementy listy muszą być tego samego typu. Nie można zatem zagnieżdżać (pod)list, chyba że zapiszemy jednolitą listę list. Poniższe przykłady ukazują poprawnie zapisane listy:

  • [1, 2, 3] — prosta lista liczb całkowitych,
  • [[1, 2, 3], [4, 5], [6]] — lista list liczb całkowitych,
  • [] — lista pusta,
  • [’a’, ’b’, ’c’] — lista znaków,
  • [”Ala”, ”ma”, ”kota”] — lista napisów.

Ogólnie, jeśli T jest typem, to [T] oznacza listę o elementach typu T. Zatem typ listy liczb całkowitych zapisuje się jako [Integer], typ listy list liczb całkowitych jako [[Integer]], a typ listy znaków — jako [Char]. Obowiązuje konwencja, że napisy są skrótową postacią list znaków, czyli np. napis ”Abc” oznacza to samo, co lista [’A’, ’b’, ’c’]. W szczególności, napis pusty to lista pusta.

Typ listowy można by skonstruować od zera, pisząc deklarację

 data List a = Nil | Cons a (List a)

Byłaby to rekurencyjna definicja typu, w której pojawia się zmienna typowa a oraz konstruktor listy pustej Nil i konstruktor Cons, dodający element na początku listy. W praktyce stosuje się notację, w której lista pusta oznaczana jest jako [], zaś konstruktor — jako dwukropek. Tak więc przykładowo listę [0, 1, 2] można „skonstruować” jako 0 : (1 : (2 : [])). Oczywiście konstruktorów [] i : używa się w definicjach rekurencyjnych z dopasowywaniem do wzorca. Klasyczny przykład to funkcja obliczająca długość listy:

 dl :: [a] -> Integer
 dl [] = 0
 dl (x:xs) = 1 + dl xs

Zauważmy, że funkcja ta działa dla list dowolnego typu — w zgodzie z oczekiwaniami i zdrowym rozsądkiem. Z drugiej strony, sprawdzanie równości dwóch list (czyli sprawdzenie element po elemencie) wymaga, byśmy potrafili sprawdzać równość pojedynczych elementów. Stąd standardowa definicja porównywania list (==) przedstawia się następująco:

 instance Eq a => Eq [a] where
     []     == []     =  True
     (x:xs) == (y:ys) =  x==y && xs==ys
     _      == _      =  False

Przytaczamy ją tu, gdyż jest pouczająca z paru powodów. Po pierwsze, zwróćmy uwagę na nagłówek: deklarujemy, że typ [a] należy do klasy Eq (jest typem „równościowym”), jeśli typ a należy do Eq. Po drugie, mamy tu dopasowywanie i rekurencję na listach. Po trzecie, w dopasowaniu mamy trzeci wariant ze zmiennymi „niemymi”, które pasują do wszystkiego; taki wariant spełnia więc rolę wariantu domyślnego, używanego jeśli poprzednie nie dały dopasowania. Zwróćmy uwagę, że ma to sens tylko wtedy, gdy warianty dopasowania rozpatrywane są w konkretnej kolejności — od góry do dołu (tak jest w Haskellu). Bez tego założenia ów trzeci wariant wchłonąłby wszystkie inne. Dla przejrzystości definicji lepiej więc stosować warianty rozłączne.

Łączenie i odwracanie list

Do łączenia (konkatenacji) list służy operator ++, np.

  • [0, 1] ++ [2, 3, 4] daje [0, 1, 2, 3, 4],
  • [’a’, ’b’] ++ [] ++ [’c’] daje [’a’, ’b’, ’c’] — co interpreter zapewne wyświetli jako ”abc”,
  • ”ab” ++ ”” ++ ”c” to to samo, co powyżej.

Łączone listy muszą być oczywiście tego samego typu.

Prosta definicja funkcji odwracającej listę mogłaby być następująca:

 odwr1 :: [a] -> [a]
 odwr1 [] = []
 odwr1 (x:xs) = odwr1 xs ++ [x]

Nietrudno jednak zauważyć, że funkcja ta działa w czasie proporcjonalnym do kwadratu długości listy. Taki wynik nas absolutnie nie zadowala. Żeby jednak zdefiniować dobrą funkcję odwracającą, musimy najpierw przyjrzeć się ogólnej postaci rekurencyjnych definicji funkcji listowych — podobnie jak to zrobiliśmy dla liczb naturalnych.

Otóż typowy schemat definicji funkcji listowych jest taki:

 f :: [a] -> b
 f [] = e
 f (x:xs) = h (x (f xs))

Tutaj e jest elementem typu b, zaś h jest funkcją o sygnaturze (a, b) -> b. Gdyby funkcję h potraktować jako operator, to — nadużywając nieco zwyczajowej notacji — wynik funkcji f na liście x = [x_1, x_2, \ldots, x_n] można by zapisać jako x_1 h (x_2 h (\ldots (x_n h e)\ldots)). Zwróćmy uwagę na nawiasowanie, które określa się mianem łączenia w prawo.

Podobnie jak to uczyniliśmy dla definicji funkcji na liczbach naturalnych, sytuację możemy ująć w postaci aplikacji specjalnej funkcji, którą tym razem nazwiemy rekdefp („p” ze względu na łączenie w prawo). Definicja rekdefp w postaci rozwiniętej wygląda tak:

 rekdefp :: (a -> b -> b) -> b -> [a] -> b
 rekdefp h e [] = e
 rekdefp h e (x:xs) = h x (rekdefp h e xs)

Otrzymujemy w ten sposób bardzo wszechstronne narzędzie. Przykładowo:

 dl :: [a] -> Integer
 dl = rekdefp dodaj1 0 where dodaj1 x n = n + 1
 odwr2 :: [a] -> [a]
 odwr2 = rekdefp sklej [] where sklej x xs = xs ++ [x]

Wciąż jednak odwr2 nie jest tą funkcją odwracającą listę, o której marzymy. Rozważmy zatem schemat podobny do poprzedniego, ale z łączeniem nawiasów w lewo. Chcemy, by wynik funkcji f na liście x = [x_1, x_2, ..., x_n] miał postać (\ldots((e h x_1) h x_2)\ldots) h x_n. Tutaj h ma sygnaturę (b, a) -> b. Niestety, tym razem nie da się schematu zapisać tak prosto jak poprzednio — to dlatego, że konstruktor list (:) dołącza nowy element z przodu listy, a nie z tyłu. Tym niemniej, rzecz ponownie możemy ująć jako uniwersalną funkcję do definiowania funkcji, rekdefl („l” ze względu na łączenie w lewo). W postaci rozwiniętej:

 rekdefl :: (b -> a -> b) -> b -> [a] -> b
 rekdefl h e [] = e
 rekdefl h e (x:xs) = rekdefl h (h e x) xs

Popatrzmy na poniższy przykład:

 odwr3 :: [a] -> [a]
 odwr3 = rekdefl złącz [] where złącz xs x = x : xs

Wreszcie zdefiniowaliśmy funkcję odwracającą listę w czasie liniowym...

Uwaga: funkcje rekdefp i rekdefl są w Haskellu standardowe i zwą się foldr i foldl. Funkcja odwracająca listę, zdefiniowana tak jak odwr3, to reverse. Ściślej, definicja jest taka:

 reverse :: [a] -> [a]
 reverse = foldl (flip (:)) []

Pojawia się tu funkcja flip, która jest drobnym a przydatnym narzędziem, służącym do odwracania kolejności argumentów. Ten przykład pokazuje, jak w programowaniu funkcyjnym użyteczne programy powstają z powiązania prostych i bardzo ogólnych idei. Patrząc na funkcje foldl, flip i (:), można odnieść wrażenie, że są to twory niesłychanie ogólne (owszem, są...) i że daleko stąd do konkretnych funkcji. Tymczasem z nich właśnie (i praktycznie niczego więcej) powstaje efektywny wariant funkcji reverse.

Operator aplikacji zbiorowej i filtrowanie list

Naturalne wydaje się zdefiniowanie operatora, który otrzymawszy funkcję i listę argumentów, aplikowałby ową funkcję do poszczególnych elementów listy. Operator taki nosi w Haskellu nazwę map i jest zdefiniowany następująco:

 map :: (a -> b) -> [a] -> [b]
 map f [] = []
 map f (x:xs) = f x : map f xs

Przykładowo, możemy napisać:

  • map (+1) [0, 1, 2] — w wyniku otrzymujemy [1, 2, 3],
  • map (>0) [–1, 0, 1, 2] — w wyniku otrzymujemy [False, False, True, True],
  • map silnia [0, 3, 6, 9] — w wyniku otrzymujemy [1, 6, 720, 362880].

Ponownie zwróćmy uwagę na prostotę definicji funkcji map, a przede wszystkim na to, że daje się ona wyrazić w samym Haskellu.

Inna charakterystyczna operacja listowa to filtrowanie. Chodzi o wybranie z listy tylko tych elementów, które spełniają podane kryterium, i zwrócenie ich jako nowej (zwykle krótszej) listy. Do filtrowania służy standardowa funkcja filter:

 filter :: (a -> Bool) -> [a] -> [a]
 filter p [] = []
 filter p (x:xs) = if p x then x : filter p xs else filter p xs

Uwaga: prawdziwa definicja stosuje zapis z kwalifikatorem (o którym powiemy za chwilę), ale jest równoważna przytoczonej powyżej:

 filter p xs = [ x | x <- xs, p x ]

Przykłady użycia:

  • filter (>0) [–1, 0, 1, 2] — w wyniku otrzymujemy [1, 2],
  • filter even [3, 4, 1, 6, 7, 9, 0] — w wyniku otrzymujemy [4, 6, 0].

Wspomnijmy więc na koniec o tworzeniu list za pomocą wyrażeń z kwalifikatorami. Otóż ogólna postać to [ wyrażenie | kwalifikator ], przy czym kwalifikator może być generatorem lub dozorem (czyli warunkiem). Całość opisuje listę w podobny sposób, jak często opisuje się zbiory, np. \{x^2 | x \in \{0, 1,\ldots , 99\}, x-\textnormal{parzyste}\}. Listę takich liczb można w Haskellu zapisać jako:

 [x*x | x <- [0..99], even x]

Generator ma postać x <- y, gdzie x jest zmienną lub n-tką zmiennych, a y — wyrażeniem listowym. Dozór to po prostu wyrażenie logiczne. Przykłady kilku wyrażeń z kwalifikatorami:

  • [(x, y) | x <- [1..4], y <- [1..5]],
  • [(x, y) | x <- [1..4], y <- [1..5 – x]],
  • [x + y | x <- [1..3], y <- [1..3]].

Drugi z tych przykładów pokazuje, że kolejny generator może korzystać z wartości z poprzedniego generatora. Trzeci przykład pozwala zauważyć, że generowane wartości nie są w żaden sposób sortowane.