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

Wprowadzenie

Kontynuujemy prezentację Haskella. W tym wykładzie zajmiemy się przede wszystkim listami, które od zarania dziejów języków funkcyjnych były jedną z ich głównych atrakcji. Powiemy też więcej o definicjach rekurencyjnych; ułatwi nam to efektywne definiowanie funkcji takich jak ciąg Fibonacciego.

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. Nota bene, 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) — z 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, są 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ąć Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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.