Paradygmaty programowania/Wykład 10: Programowanie funkcyjne w Haskellu I

From Studia Informatyczne

Spis treści

Wstęp

O powodach, dla których interesujemy się językami funkcyjnymi, pisaliśmy już we wcześniejszych wykładach. Przypomnijmy więc tylko krótko, że jedną z ważnych motywacji jest oderwanie się od klasycznej architektury von Neumanna, czyli uniezależnienie programowania od sprzętu komputerowego, jakim dysponujemy (bo może niebawem będziemy mieli zupełnie inny?). Zwrócenie się ku funkcjom w postaci takiej, jaką matematycy znają od wielu lat, jest w tym układzie dość naturalne — jest to formalizm bardzo dobrze ugruntowany, z olbrzymim zasobem gromadzonej przez lata wiedzy, a przy tym nie uwikłany w uwarunkowania techniczne tak jak języki imperatywne.

Z drugiej strony, wielu mogłoby sądzić, że programowanie za pomocą „samych funkcji” to po prostu ograniczenie istniejących możliwości języków programowania do pewnego egzotycznego podzbioru. Zapewne niejeden programista wyobraża sobie napisanie programu bez funkcji, ale nie wyobraża go sobie bez instrukcji podstawienia... Jednakże programowanie funkcyjne to coś więcej niż zwykły język zawężony do funkcji. Choć można właściwie powiedzieć, że każdy typowy język programowania zawiera w sobie pewien prosty język funkcyjny, to „prawdziwe” języki funkcyjne oferują znacznie większe możliwości.

Liczymy, że wykłady o Haskellu pozwolą Czytelnikowi zobaczyć owe dodatkowe możliwości języków funkcyjnych. Dodajmy, że w odróżnieniu od wykładu przeglądowego, gdzie użyliśmy pewnych uproszczeń w prezentowaniu Haskella, tu będziemy się starali wiernie odwzorować jego składnię i semantykę.

Na koniec wstępu ważna informacja i zarazem zachęta. Otóż na stronie www.haskell.org można znaleźć mnóstwo informacji o Haskellu, jak również odnośniki do miejsc, skąd można pobrać darmowe interpretery i kompilatory Haskella.


Sposób pracy z Haskellem

W odróżnieniu od typowych języków kompilowanych, Haskell pozwala na pracę interaktywną. Praca taka, zwana sesją, polega na wpisywaniu wyrażeń, które Haskell oblicza i wypisuje ich wynik. Zatem w najprostszym przypadku możemy używać Haskella podobnie jak kalkulatora:

? 7*8
56

Oczywiście, gdyby całość zamykała się w tak pojętej współpracy, trudno byłoby mówić o jakimkolwiek programowaniu. Fundamentalna cecha Haskella, która różni go od zwykłego kalkulatora, to możliwość tworzenia definicji złożonych funkcji, które później wykorzystujemy w obliczeniach. Zbiór definicji podanych Haskellowi, oczywiście w odpowiedniej dla niego składni, zwany jest skryptem. Typowo skrypt zapisuje się w pliku z rozszerzeniem .hs. Przykładowy skrypt może wyglądać następująco:

skl :: Integer -> Integer
skl x = x * (x +1) `div` 2

Jest to definicja funkcji obliczającej sumę kolejnych liczb całkowitych od 1 do x. Definicja składa się z dwóch istotnych części (w wykładzie przeglądowym pomijaliśmy pierwszą z nich):

  • Pierwsza to opis typu funkcji. W tym przypadku jest to funkcja, która bierze jako argument liczbę całkowitą i zwraca również liczbę całkowitą. Opis typu można pominąć, jeśli nie prowadzi to do niejednoznaczności.
  • Druga część to sposób wyliczenia wartości funkcji. Poza zwykłymi elementami, znanymi z większości języków programowania, mamy tu zabawnie zapisany operator div, oznaczający dzielenie całkowite, ujęty w odwrócone apostrofy. Dla uniknięcia niejednoznaczności tak zapisuje się operatory, które nie są wyrażone symbolami +*/ itp.

W wielu sytuacjach składnia Haskella pozwala obejść się bez znaków średników i przecinków; ich rolę spełnia odpowiedni układ tekstu. Taki właśnie sposób zapisu będziemy na ogół stosowali w przykładach.

Oczywiście zdefiniowaną przez siebie funkcję można wykorzystać w sesji, np.

? skl 4
10
? skl 100
5050

W ogólności skrypty wraz z bibliotekami standardowymi tworzą środowisko, w którym zdefiniowane są pewne funkcje. Ściślej — nazwy powiązane są z definicjami. Wyrażenie, które wpisujemy w interpreterze, może z tych definicji korzystać.

Zauważmy, że definicja funkcji to właściwie równanie wiążące dwa wyrażenia. Takie ujęcie pozwala pisać definicje, które nie miałyby racji bytu w konwencjonalnych językach, np.

nieskończoność :: Integer
nieskończoność = nieskończoność + 1

Choć z tej definicji nie da się wyliczyć żadnej konkretnej liczby, to Haskell może ją wykorzystać jako pewnego rodzaju regułę przekształcania wyrażeń.

Wspomnijmy tutaj jeszcze o ciekawej cesze arytmetyki na liczbach całkowitych w Haskellu. Otóż wielkość liczb nie jest ograniczona od góry przez język. Pewne ograniczenie narzuca rozmiar pamięci komputera, ale w praktyce oznacza to, że można działać na naprawdę kolosalnych liczbach. Bez trudu można policzyć np. silnię z tysiąca, a nawet więcej...

Co właściwie robi interpreter? Jaki to ma związek z nieskończonością?

Wczytawszy wyrażenie, interpreter stara się zredukować je do reprezentacji kanonicznej. W praktyce oznacza to wypisanie liczby w notacji dziesiętnej, napisu itp. — to są bowiem kanoniczne reprezentacje dla przykładowych typów danych. Nie zawsze jednak istnieje kanoniczna reprezentacja wyliczonej wartości. Jeśli wynikiem obliczeń jest funkcja (a nie jej wartość w jakimś punkcie), to nie ma co wypisać... Inna sytuacja, gdy nie otrzymamy wyniku na ekranie, to oczywiście obliczenia nieskończone. Przykładem takich obliczeń mogłoby być nieostrożne użycie definicji nieskończoności:

? skl nieskończoność

lub po prostu

? nieskończoność

Tego rodzaju obliczenia albo będą trwały bez końca, albo zakończą się komunikatem o braku pamięci (z powodu przepełnienia stosu).

Jednak nie każde użycie tej fatalnej definicji prowadzi do błędu. Jeśli zdefiniujemy specjalny wariant mnożenia jak poniżej, to mnożenie przez zero zawsze zwróci zero, nawet jeśli drugim argumentem będzie nieskończoność (inna sprawa, czy to jest rozsądna definicja).

mnóż :: (Integer, Integer) -> Integer
mnóż (x, y) = if x == 0 || y == 0 then 0 else x * y

Takie działanie zawdzięczamy obliczaniu leniwemu, czyli obowiązującej w Haskellu zasadzie, że obliczenia wykonuje się dopiero wtedy, gdy są konieczne. Powyższy przykład ukazuje ten mechanizm w prostej sytuacji, analogicznej do tego, co znają programiści piszący w języku C i pochodnych — drugi składnik alternatywy (||) nie jest wyliczany, jeśli już pierwszy pozwala określić wartość wyrażenia.

W tym miejscu warto powiedzieć o bardzo ważnej właściwości Haskella, wspólnej dla wszystkich języków funkcyjnych. Otóż funkcje są tu bytami traktowanymi na (niemal...) równych prawach ze zwykłymi, prostymi wartościami. A więc można pisać funkcje, które biorą inne funkcje jako argumenty i zwracają funkcje — czyli można pisać funkcje wyższego rzędu. Oto przykład:

iter :: (Integer, Integer -> Integer) -> (Integer -> Integer)
iter (0, f) x = x
iter (n, f) x = f (iter (n - 1, f) x)

Funkcja ta tworzy iteraty podanej funkcji typu całkowitego. Innymi słowy, zamiast pisać skl (skl (skl 2)), możemy pisać iter (3, skl) 2. Zauważmy, że choć w definicji funkcji iter działamy na elementach, to w efekcie dostajemy funkcję, która zwraca funkcję, a nie konkretną liczbę całkowitą — np. iter (3, skl) jest prawdziwą funkcją i można jej użyć jako argumentu dla iter... A zatem obydwa poniższe wyrażenia dają taki sam wynik:

iter (4, iter (3, skl)) 2
iter (12, skl) 2

Jak zapisywać definicje?

Alternatywą dla konstrukcji warunkowych if-then-else jest zapis definicji z dozorami, przydatny zwłaszcza wtedy, gdy definicja funkcji obejmuje kilka przypadków. Przykładowo:

sgn1 :: Integer -> Integer
sgn1 n = if n > 0 then 1 else if n == 0 then 0 else -1
sgn2 :: Integer -> Integer
sgn2 n
  | n > 0   = 1
  | n == 0  = 0
  | n < 0   = -1

Kolejna konstrukcja, która pozwala rozważać różne przypadki, to dopasowywanie do wzorca. Można je zresztą łączyć z innymi konstrukcjami, np.

sgn3 :: Integer -> Integer
sgn3 0 = 0
sgn3 n
  | n > 0   = 1
  | n < 0   = -1

Tutaj pierwszym wzorcem jest po prostu liczba zero. Jeśli parametr aktualny do niej pasuje (czyli jest zerem), to wykorzystywany jest ten właśnie wariant definicji. Drugi wzorzec to n, do którego pasuje każda liczba.

Definicja może zawierać definicję lokalną, w której przeprowadzamy część obliczeń. Definicję lokalną wprowadza się za pomocą where:

rkwadrat :: (Float, Float, Float) -> (Float, Float)
rkwadrat (a, b, c) = if delta < 0 then (0, 0)
  else ((- b + sqrt delta)/dwaa, (- b - sqrt delta)/dwaa)
  where delta = b*b - 4*a*c; dwaa = 2*a

Przy sposobności zwróćmy uwagę na to, że definiujemy funkcję zwracającą parę liczb typu Float. Float to oczywiście standardowy typ zmiennoprzecinkowy — nie ma tu tak komfortowego rozwiązania, jak w dla liczb całkowitych.

Składanie funkcji

W bardzo wielu przypadkach nie jest potrzebne jawne zapisywanie składania funkcji, mimo że w języku funkcyjnym to przecież fundamentalna operacja... Jest tak po pierwsze dlatego, że złożenia często definiujemy za pomocą wartości na elementach, a wówczas nie potrzebujemy jawnego operatora składania. Po drugie, programowanie na poziomie funkcji wyższego rzędu niejednokrotnie eliminuje potrzebę składania funkcji na rzecz aplikowania funkcji do funkcji.

Tym niemniej, jeśli chcemy jawnie zapisać składanie funkcji, możemy to zrobić za pomocą kropki. Typy składanych funkcji muszą się odpowiednio zgadzać, tzn. żeby można było złożyć g.f, wynik f musi być zgodny z typem argumentu funkcji g.

Funkcję iter możemy więc zapisać tak:

iter :: (Integer, Integer -> Integer) -> (Integer -> Integer)
iter (0, f) = id
iter (n, f) = f . iter (n - 1, f)

Dostajemy dokładnie taką samą funkcję jak poprzednio — ale z bardziej przejrzystą definicją. Nota bene, jak nietrudno się domyślić, funkcja id to tożsamość, działająca dla dowolnego typu.

Typy

Każdy Czytelnik, który dotarł do tego miejsca, z pewnością już wie, że typy są bardzo ważne — zwłaszcza w języku funkcyjnym. Ich istota jest taka sama jak w innych językach, natomiast znacznie większa jest obfitość operacji na typach.

Haskell jest językiem silnie typowanym. Przypomnijmy, że oznacza to, iż wykrywane są wszystkie niezgodności typów (zgodność może być czasem rezultatem niejawnej konwersji, np. z typu Integer do Float). Zasadę tę można też równoważnie sformułować tak: typ każdego wyrażenia daje się wyprowadzić z typów jego składników.


Typy polimorficzne

Wydaje się, że sztywne przyporządkowanie typów funkcjom jest niekiedy nadmiernym ograniczeniem. Rozważmy przykład funkcji podnoszącej liczbę x do kwadratu:

kw :: Integer -> Integer
kw x = x * x

Zdecydowanie chcielibyśmy, by funkcja ta była polimorficzna — przecież dla dowolnego typu liczbowego wygląda tak samo... I rzeczywiście, można zdefiniować ją jako polimorficzną:

kw :: Num a => a -> a
kw x = x * x

W zapisie tym a jest zmienną typową, której zakres ograniczamy przez klauzulę „Num a =>”, oznaczającą klasę typów liczbowych: Integer, Float, Double i parę innych. Zatem funkcja kw podnosi do kwadratu dowolną liczbę, a wynik ma taki sam typ jak argument. Polimorficzna może być nawet stała:

sto :: Num a => a
sto = 100

Są funkcje, gdzie ograniczanie zakresu zmiennej typowej w ogóle nie jest potrzebne, gdyż mogą działać dla dowolnego typu. Taka jest np. funkcja iter; możemy więc zapisać ją w bardziej ogólnej postaci:

iter :: (Integer, a -> a) -> (a -> a)
iter (0, f) = id
iter (n, f) = f . iter (n - 1, f)

Rozwijanie funkcji wieloargumentowych

Wywołanie funkcji dwuargumentowej zapisuje się w postaci f(x, y). Nawiasy są tu konieczne, gdyż zapis f x y byłby interpretowany jako (f x) y. Tak więc jeśli nie chcemy pisać nawiasów, musimy sprawić, by f x było funkcją, którą można by zaaplikować do y. Przyjrzyjmy się, co mamy, a co chcielibyśmy mieć; jako przykładowego typu użyjemy typu Integer:

Mamy:

f1 :: (Integer, Integer) -> Integer

Chcielibyśmy mieć:

f2 :: Integer -> (Integer -> Integer)

Funkcja f2 to oczywiście funkcja jednoargumentowa, której wynikiem jest kolejna funkcja jednoargumentowa. Dzięki temu (i dzięki regułom interpretacji wyrażeń — funkcje aplikuje się od lewej do prawej) zapis f2 x y będzie poprawny. Jak przerobić posiadaną funkcję f1 na f2? Wystarczy do powyższej sygnatury dopisać definicję:

f2 x y = f1 (x, y)

Podobnie jak w pierwszym wariancie funkcji iter, funkcję f2 definiujemy dla konkretnego elementu, ale otrzymujemy funkcję zwracającą funkcje.

Tego rodzaju rozwijanie funkcji dwuargumentowych jest na tyle przydatne, że istnieje standardowa funkcja do rozwijania funkcji. Jest to polimorficzna funkcja o nazwie curry (ponownie na cześć Haskella Curry’ego). Jej definicja jest zresztą bardzo prosta:

curry :: ((a, b) -> c) -> (a -> b -> c)
curry f x y = f (x, y)

Zwróćmy uwagę na polimorficzną sygnaturę. Wynik funkcji curry ma typ a -> b -> c, co — na mocy konwencji — należy rozumieć jako a -> (b -> c). Jest też funkcja uncurry, służąca do „zwijania”:

uncurry :: (a -> b -> c) -> ((a, b) -> c)
uncurry f p = f (fst p) (snd p)

Funkcje fst i snd służą do wydzielenia pierwszego i drugiego elementu pary.

Nowe typy i klasy typów

Operując typami polimorficznymi, często potrzebujemy zawęzić klasę typów, które dopuszczamy w danym kontekście. Tak było, gdy definiowaliśmy funkcję kw, podnoszącą liczbę do kwadratu. Użyliśmy definicji polimorficznej, w której typ argumentu i wyniku musiał pochodzić z klasy Num. Zauważmy, że sygnatura kw :: Num a => a -> a dopuszcza w miejscu a dowolny typ liczbowy (tzn. z klasy Num), ale musi to być ten sam typ po obydwu stronach — nie może to być np. Float -> Integer.

Num jest jedną z predefiniowanych klas typów. Inne przykładowe klasy to: Eq — klasa typów, dla których zdefiniowane jest porównywanie (operatory == i /=), Show — klasa typów, których wartości można wypisywać na ekranie, Enum — klasa typów wyliczeniowych (dla których muszą istnieć m.in. operacje brania poprzednika i następnika). Użytkownik może definiować własne klasy, wskazując jakie operacje muszą być określone dla typów do danej klasy należących. Poniższy przykład, zaczerpnięty ze standardowej biblioteki Haskella (a ściślej z tzw. preludium), to główny fragment definicji klasy Num:

class (Eq a, Show a) => Num a where
  (+), (-), (*)  :: a -> a -> a
  negate         :: a -> a
  abs, signum    :: a -> a
  fromInteger    :: Integer -> a
  fromInt        :: Int -> a

Definicja ta mówi, że typy z klasy Num muszą spełniać założenia klas Eq i Show (w języku programowania obiektowego powiedzielibyśmy, że Num jest podklasą klas Eq i Show) oraz muszą posiadać wymienione tu operacje.

Konkretne instancje typów wprowadza się następnie za pomocą instance. Poniżej przykład deklaracji, która zgłasza typ Int jako instancję klasy Eq, w której do porównania służy wbudowana funkcja primEqInt:

instance Eq Int where (==) = primEqInt

Klasy typów nie muszą być rozłączne ani nie muszą tworzyć łańcuchów w sensie zawierania.

Nowe typy można wprowadzać na wiele sposobów. Jednym z nich jest iloczyn kartezjański, czyli łączenie istniejących typów w pary i — ogólniej — n-tki. Dowolna definicja funkcji n-argumentowej to przykład n-tki typów. Oznaczeniem takiego typu są nazwy typów składowych w nawiasach, rozdzielone przecinkami. Inny przykład konstruowania typów będziemy mieli okazję zobaczyć np. przy omawianiu list. Chodzi tu o listę elementów danego typu — nowy typ oznaczany jako [T], gdzie T jest typem elementów listy. Pamiętajmy wreszcie, że operator -> używany w sygnaturach funkcji służy do określania ich typów. Jako że dopuszczalne są funkcje wyższego rzędu, typy tworzone za pomocą -> mogą być złożone (por. definicje funkcji iter i curry).

Wymieńmy zatem parę przykładowych typów:

  • (Integer, Integer, Float) to typ, do którego należą wiadome trójki liczb.
  • (Integer -> Integer) -> (Integer -> (Integer -> Integer)) to typ funkcji, która jako argument bierze funkcję i zwraca funkcję, która bierze liczbę i zwraca funkcję...
  • [Integer] to typ „lista liczb całkowitych”.

Dodajmy, że jeśli chcemy nadać nazwę złożonemu typowi (np. po to, by uprościć zapis), to można to zrobić za pomocą deklaracji type, np.

type MojeF = (Integer -> Integer) -> (Integer -> (Integer -> Integer))

Nazwa typu powinna rozpoczynać się od dużej litery. Nieco inną semantykę ma — podobna składniowo — deklaracja newtype. Tworzy ona nowy typ o identycznej reprezentacji, ale traktowany jako różny od „starego”, np.

newtype NowyInteger = Integer

Jak definiuje się operatory?

Duża część operatorów dwuargumentowych jest polimorficzna i obsługuje całą klasę typów. Przykładowo, operatory dodawania i mnożenia obsługują typy z klasy Num; operator dzielenia działa w klasie Fractional (jest to podklasa klasy Num); operatory `div` i `mod` działają w klasie Integral (podklasa klas Enum i Real, a pośrednio także klasy Num). Są jednak również operatory monomorficzne, np. && oraz ||, które standardowo działają w typie Bool i żadnym innym.

Ciekawy jest sposób definiowania i używania operatorów dwuargumentowych. Otóż operatorem jest każda funkcja o sygnaturze a -> a -> a, gdzie a jest pewnym typem, polimorficznym lub zwykłym. Innymi słowy sygnatura operatora może wyglądać np. tak:

Integer -> Integer -> Integer
Num a => a -> a -> a

Obowiązuje następująca konwencja notacyjna:

  • Jeśli nazwa takiej funkcji jest „zwykła” (tzn. składa się z liter, cyfr i ewentualnie znaków podkreślenia), to funkcji tej można używać w zwykły sposób, np. div 7 4, a po ujęciu jej nazwy w odwrócone apostrofy — w notacji infiksowej, np. 7 `div` 4.
  • Jeśli nazwa funkcji składa się z symboli, to w definicji należy ująć ją w nawiasy okrągłe. Wówczas funkcji tej używa się w notacji infiksowej, np. 7 + 4, a po ujęciu w nawiasy — w zwykłej, np. (+) 7 4.

Zauważmy, że w obydwu przypadkach użycie zwykłej notacji funkcyjnej odnosi się do funkcji w postaci rozwiniętej, a więc dobre są wywołania (+) 7 4 oraz div 7 4, a nie (+) (7, 4) bądź div (7, 4).

Załóżmy zatem, że postawiliśmy następujące definicje:

(%%%) :: Integer -> Integer -> Integer
(%%%) x y = x + 5 * y
abc :: Integer -> Integer -> Integer
abc x y = 2 * x + y * y

Wszystkie poniższe wywołania są wówczas dozwolone:

3 %%% 7
(%%%) 3 7
3 `abc` 7
abc 3 7

Można powiedzieć, że ujęcie typowego operatora w nawiasy zamienia go w zwykłą funkcję, a ujęcie funkcji w odwrócone apostrofy zamienia ją w operator — oczywiście pod warunkiem, że mają właściwy typ i liczbę argumentów.

Z nawiasami okrągłymi wiąże się jeszcze jedna konwencja. Otóż wraz z operatorem można ująć w nawiasy jeden argument. Otrzymujemy w ten sposób funkcję, w której jeden argument „już jest” — czyli w rezultacie funkcję jednoargumentową. Zatem np. (+4) to jednoargumentowa funkcja dodająca 4, a (`div` 3) — dzieląca przez 3. Wolno wywołać:

(+4) 3
(`div` 3) 8
(`div` 3) ((+4) 8)
((`div` 3).(+4)) 8

Ostatnie dwa wyrażenia to oczywiście to samo, co (8 + 4) div 3.