Paradygmaty programowania/Wykład 12: Programowanie funkcyjne w Haskellu III

From Studia Informatyczne

Spis treści

Listy nieskończone

Do tej pory o listach nieskończonych uczyniliśmy zaledwie przelotną wzmiankę. Pojawiły się one w paru przykładach, takich jak [0..], [2, 4..], [ n*n | n <- [0..]]. Przypomnijmy najpierw, skąd mogą się pojawić listy nieskończone.

Definiowanie list nieskończonych

Pierwsza możliwość to nieskończony ciąg arytmetyczny, zapisany za pomocą dwóch kropek. Możliwe są dwie sytuacje:

  • Ciąg o różnicy 1: wystarczy podać pierwszy element, np. [1..], [–123..].
  • Ciąg o innej różnicy: trzeba podać dwa pierwsze elementy, np. [1, 3..], [0, 3..].

Druga możliwość powstaje w wyniku użycia zapisu z kwalifikatorem, jak w powyższym [ n*n | n <- [0..]]. Zauważmy, że w praktyce w takim wyrażeniu potrzebny jest generator, za którym — prędzej czy później — czai się ciąg arytmetyczny.




Trzecia możliwość bierze się z rekurencyjnych definicji struktur danych. Rozważmy następującą definicję:

 zera :: [Integer]
 zera = 0 : zera


Tworzymy tu nieskończoną, rekurencyjną strukturę — listę złożoną z samych zer. Ciekawostką niech będzie sposób reprezentowania tej struktury w Haskellu. Otóż generalnie wyrażenia są reprezentowane w postaci grafów; w tym przypadku jest to prosty graf cykliczny, pozwalający zapisać tę listę w skończonej (bardzo niewielkiej) pamięci. Podobną definicję i reprezentację ma poniższy nieskończony napis:

 hasło :: String
 hasło = ”Duc” ++ reszta
   where reszta = ” in altum” ++ reszta

Wykorzystanie list nieskończonych w obliczeniach

Rzecz jasna nie chodzi o nakłanianie Haskella do prowadzenia obliczeń w nieskończoność. To zresztą jest proste — wystarczy wpisać zdefiniowaną powyżej nazwę „zera”, by Haskell zaczął w nieskończoność wypisywać owe zera. Ponieważ reprezentacja jest tu cykliczna i nie jest potrzebne pamiętanie historii obliczeń, nie będzie nawet okazji do przepełnienia stosu...

Trzeba zachować pewną dozę ostrożności, by zrobić użytek z list nieskończonych. Przede wszystkim pamiętajmy, że zapis z użyciem kwalifikatorów to nie to samo, co typowe teoriomnogościowe opisy zbiorów. Przykładowo, jest dla każdego oczywiste, że zbiór \{x^2 | x \in \{0, 1, 2, ...\}, x^2 < 50\} jest skończony. Jeśli jednak zapiszemy pochopnie w Haskellu [x*x | x <- [0..], x*x < 50], to przekonamy się, że interpreter wypisuje żądane kwadraty od 0 do 49, a następnie tkwi w nieskończonej pętli. Nie oczekujmy, że interpreter będzie potrafił rozpoznać takie sytuacje. W istocie musiałby on umieć udowodnić, że po przetworzeniu x = 7 żadna następna wartość x nie da kwadratu mniejszego niż 50.

Powyższą sytuację da się jednak okiełznać. Zamiast zapisywać dozór (x*x < 50) w definicji listy, użyjmy funkcji takeWhile, która działa podobnie do omawianej już funkcji filter. Różnica polega na tym, że po natrafieniu na element, który nie spełnia postawionego warunku, dalsze elementy już nie są brane pod uwagę. Zauważmy, że naszą intencję zawartą w definicji [x*x | x <- [0..], x*x < 50] można też wyrazić przez:

 filter (<50) (map kw [0..]) where kw x = x*x

Zastąpienie filter przez takeWhile daje pożądany rezultat, czyli listę [0, 1, 4, 9, 16, 25, 36, 49]:

 takeWhile (<50) (map kw [0..]) where kw x = x*x

Zauważmy, że używając funkcji takeWhile, przekazujemy Haskellowi naszą wiedzę o tym, iż po natrafieniu na kwadrat większy lub równy 50, nie trzeba kontynuować obliczeń.

Jak działa obliczanie leniwe?

Wykorzystanie list nieskończonych to dobra sposobność do przyjrzenia się obliczaniu leniwemu, stosowanemu przez Haskella. Zasadnicze pytanie brzmi: jak interpreter ustala, co będzie obliczane, a co nie?

Kluczową rolę odgrywa tutaj kolejność przekształcania wyrażeń, a ściślej — redukowania poszczególnych fragmentów zgodnie z posiadanymi definicjami. Fragment wyrażenia, który da się zredukować, zwany jest redeksem. Otóż Haskell najpierw redukuje najbardziej zewnętrzny redeks, czyli taki, który nie jest częścią innego redeksu. Zatem jeśli w którymś momencie pewien fragment wyrażenia okaże się niepotrzebny (np. pierwszy element pary, gdy wykorzystujemy tylko drugi), to interpreter nie zagłębia się dalej.

Rozważmy obliczanie wyrażenia kw (snd ([1..], 2)). Kolejne redukcje będą przebiegały tak:

 kw (snd ([1..], 2))
    -- z definicji kw
 (snd ([1..], 2)) * (snd ([1..], 2))
    -- z definicji snd
 2 * (snd ([1..], 2))
    -- z definicji snd
 2 * 2
    -- z definicji *
 4

Najciekawsza jest tu oczywiście redukcja wyrażenia snd ([1..], 2) do 2 bez zagłębiania się w obliczanie [1..]. Zauważmy, że przy opisanej tu kolejności redukcji możemy otrzymać wynik dla wielu wyrażeń, dla których przy innej kolejności wyniku byśmy nie dostali (gdyż interpreter utknąłby w nieskończonych obliczeniach). Jeśli jednak dotarlibyśmy do końca obliczeń, to wynik byłby taki sam.

W powyższym przykładzie dokonaliśmy istotnego uproszczenia (?); zredukowawszy wyrażenie kw (snd ([1..], 2)) zgodnie z definicją funkcji kw, zapisaliśmy dwie kopie wyrażenia snd ([1..], 2). Tymczasem naprawdę Haskell robi inaczej — reprezentuje wyrażenie w postaci grafu, gdzie wspólne podwyrażenia pojawiają się jednokrotnie, natomiast prowadzą do nich dwa (lub więcej) odniesienia. To pozwala uniknąć wielokrotnego obliczania tych samych (pod)wyrażeń. Nasz przykład powinniśmy więc zapisać tak jak poniżej, pamiętając, że w drugim kroku mamy do czynienia nie z dwoma osobnymi wyrażeniami snd ([1..], 2), lecz z jednym, do którego prowadzą dwa odniesienia.

 kw (snd ([1..], 2))
    -- z definicji kw
 (snd ([1..], 2)) * (snd ([1..], 2))
    -- z definicji snd
 2 * 2
    -- z definicji *
 4

Uważny Czytelnik zapewne spostrzeże, że w tym przykładzie dzięki obliczaniu leniwemu udało się uniknąć wyliczania listy [1..] — ale trudno to nazwać wykorzystaniem listy nieskończonej... Gdzie jest więc prawdziwe wykorzystanie owych list? Dobry przykład to wspomniane wcześniej użycie funkcji takeWhile:

 takeWhile (<50) (map kw [0..]) where kw x = x*x

Zauważmy, że taka konstrukcja pozwala nam wyrazić warunek zakończenia obliczeń za pomocą wartości wyliczanej funkcji, a nie jej argumentu. Innymi słowy, nie musimy z góry wiedzieć, dla jakich argumentów zostanie osiągnięta interesująca nas graniczna wartość funkcji — a dla funkcji bardziej skomplikowanych niż kw może to być całkiem nieoczywiste. Jednocześnie pozostajemy przy czystym programowaniu funkcyjnym w dobrym stylu, bez sztucznego imitowania konstrukcji iteracyjnych.

Podsumujemy zatem, co jest sednem obliczania leniwego:

  • Przy redukowaniu wyrażenia, najpierw redukowane są najbardziej zewnętrzne redeksy.
  • Każde podwyrażenie wyliczane jest co najwyżej raz. Nawet jeśli do jakiegoś podwyrażenia występuje więcej odwołań (jak np. po zredukowaniu funkcji kw), to są one reprezentowane jako odniesienia do jednego, wyliczanego jednokrotnie wyrażenia.

Dodajmy, że popularna uproszczona definicja obliczania leniwego — „oblicza się tylko to, co jest potrzebne” — jest realizowana przez pierwszą z powyższych zasad. Ten sposób redukowania wyrażeń pomija po prostu niepotrzebne w danej sytuacji fragmenty. Żeby jednak tak się stało, funkcje muszą być definiowane z rozmysłem, by nie zaprzepaścić dobrej woli interpretera. Otóż standardowa definicja operatora koniunkcji && jest następująca:

 (&&) :: Bool -> Bool -> Bool
 False && x  = False
 True  && x  = x

Widać więc, że jeśli dopasowanie trafi na pierwszy przypadek (pierwszy czynnik równy False), to nastąpi od razu redukcja do False, bez wyliczania wartości x. W przeciwnym razie (pierwszy czynnik równy True) wartością koniunkcji jest po prostu x, który musi być zatem wyliczony. Rozważmy teraz przykład definicji operatora podobnego do &&, ale działającego na liczbach całkowitych. Załóżmy, że jako False stosujemy 0, a jako True — 1, przy czym dowolną liczbę różną od zera traktujemy jako True.

 nibykon :: Integer -> Integer -> Integer
 nibykon x y = if x*y /= 0 then 1 else 0

Jest to definicja jasna, prosta i fatalna — gdyż „nieleniwa”. W każdym przypadku obliczane będą obydwa argumenty. Lepsza byłaby zatem definicja skonstruowana tak jak standardowa definicja operatora && lub po prostu jawne odwołanie wykorzystujące gotowy „leniwy” operator, np.

 nibykon2 x y = if x /= 0 && y /= 0 then 1 else 0

Na koniec rozważań o leniwości (lenistwie?) zauważmy, że argumenty nie są tu (i nie mogą być) traktowane symetrycznie. Musimy w definicji ustalić jeden argument (zwykle jest to ten pierwszy), którego wartość determinuje dalszy przebieg wydarzeń, tzn. czy drugi argument będzie wyliczany, czy nie.

Łączenie w n-tki

Przypomnijmy klasyczny przykład zastosowania techniki łączenia w n-tki (tutaj: w pary), a mianowicie efektywne wyliczanie wyrazów ciągu Fibonacciego.

 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

Istotą tej techniki jest rozszerzenie wyniku funkcji, przez co w wywołaniach rekurencyjnych mamy do dyspozycji więcej informacji. Na koniec możemy wybrać z n-tki tylko tę wartość, która jest zasadniczym celem obliczeń.

Zauważmy, że w przypadku ciągu Fibonacciego ta technika daje nam olbrzymi wzrost efektywności: od złożoności wykładniczej do liniowej. W poniższym przykładzie poprawa złożoności czasowej nie jest co prawda tak spektakularna (o ile w ogóle jest), ale za to osiągamy poprawę złożoności pamięciowej.

Rozważmy funkcję śr, która otrzymuje listę liczb typu Float i zwraca ich średnią arytmetyczną. Wykorzystujemy tu funkcje suma i dl, które obliczają sumę elementów listy i długość listy. Najprostsza definicja mogłaby być taka:

 śr :: [Float] -> Float
 śr x = (suma x)/(dl x)

Wadą tej funkcji jest jednak dwukrotne wykorzystanie listy x w trakcie obliczeń. Nie pociąga to wprawdzie dwukrotnego jej magazynowania w pamięci (mówiliśmy o tym niedawno w kontekście obliczeń leniwych), ale zmusza interpreter do posiadania reprezentacji całej listy. Tymczasem przy sprytnej implementacji funkcji uśredniającej interpreter może w ogóle nie potrzebować owej listy in extenso. Przyjrzyjmy się zatem owej implementacji, opartej o łączenie w pary. Otóż najpierw definiujemy funkcję sumadl, która wylicza parę (suma, długość) dla coraz dłuższych fragmentów wejściowej listy. Następnie wystarczy podzielić otrzymaną sumę przez długość. Zauważmy, że obliczenie to ma sens tylko dla niepustej listy wejściowej, stąd funkcja sumadl będzie zdefiniowana dla niepustych list. W szczególności, dopasowanie do wzorca x:y:ys działa dla list co najmniej dwuelementowych.

 sumadl :: [Float] -> (Float, Integer)
 sumadl [x] = (x, 1)
 sumadl (x:y:ys) = (x+z, n+1) where (z, n) = sumadl (y:ys)
 śr :: [Float] -> Float
 sr x = z / (fromInteger n) where (z, n) = sumadl x

Wejście-wyjście z użyciem monad

Jak pogodzić operacje wejścia-wyjścia (we-wy), których istotą są „efekty uboczne” w postaci wypisania lub wczytania tekstu z klawiatury, z programowaniem funkcyjnym, w którym efektów ubocznych być nie powinno? Idea jest następująca: zamiast mówić o „wypisywaniu na ekran” lub „czytaniu z klawiatury”, mówmy o wartościach specjalnego typu „wejściowo-wyjściowego” IO. Potrzebujemy zatem zestawu funkcji, które dają wyniki owego typu. Jeśli chcemy zaprogramować sekwencję operacji we-wy, to funkcje do tego służące będą przekazywały sobie wartości typu IO. Sednem sprawy jest tu kolejność operacji: w języku funkcyjnym kolejność obliczeń wynika jedynie z zależności między danymi; w przypadku operacji we-wy chcemy pewną kolejność wymusić.

Twór, który w Haskellu pozwala na takie traktowanie we-wy, zwany jest monadą we-wy. Z praktycznego punktu widzenia jest to typ IO (ściślej — rodzina typów IO a), dla którego są określone m.in. takie operacje: putChar, putString, print, getChar, getLine oraz dwie szczególne: >>= i return. Dodatkowo istnieje konwencja składniowa (z użyciem „do”), która pozwala zapisywać ciągi operacji we-wy w postaci podobnej do ciągów instrukcji w językach imperatywnych.

Znaczenie operacji takich jak putChar, getChar lub print jest raczej oczywiste. W szczególności funkcja print wypisuje wartość dowolnego typu z klasy Show (czyli takiego, dla którego jest określona metoda show). Mniej oczywisty jest sposób wkomponowania ich w system typów Haskella. Przyjrzyjmy się paru przykładom sygnatur:

 putChar   :: Char -> IO ()
 putStr    :: String -> IO ()
 print     :: Show a => a -> IO ()
 putStrLn  :: String -> IO ()
 getChar   :: IO Char
 getLine   :: IO String

Funkcje „wyjściowe” zwracają wynik typu IO (), gdzie () oznacza typ pusty (nota bene, jest to konstrukcja istniejąca zupełnie niezależnie od IO). Funkcje „wejściowe” zwracają wynik typu IO a, gdzie a jest typem wczytywanej wartości.

Przekazywanie wartości typu IO, o którym wspomnieliśmy na początku, dokonuje się za pomocą operatora >>=. Przykładowo:

 getChar >>= putChar

Generalnie operator >>= przekazuje wynik pierwszej operacji jako argument dla drugiej. Jeśli wynik ten nie jest interesujący, np. gdy jest pusty, używa się operatora >>. Można zatem powiedzieć, że operatory >>= i >> spełniają podobną rolę jak średnik w językach imperatywnych.

Rolę return objaśnimy w kontekście ciągów operacji we-wy zapisywanych z do. Załóżmy, że chcemy zdefiniować funkcję readln, która czyta i zwraca wiersz z klawiatury, czyli ciąg znaków zakończonych znakiem ‘\n’. Definicja mogłaby wyglądać tak (standardowa funkcja readLn zdefiniowana jest nieco inaczej — głównie dlatego, że korzysta z innych, wcześniejszych definicji):

 readln :: IO String
 readln = do c <- getChar
             if c == '\n'
               then return []
               else do cs <- readln
                       return (c:cs)

Powyższą definicję można bez trudu zrozumieć na bazie wiedzy o językach imperatywnych. Jak widać, return służy do zwrócenia wartości, natomiast strzałka <- pozwala związać wartość ze zmienną. Funkcji readln można teraz użyć np. w poniższym niezbyt wyrafinowanym programie:

 readln >>= putStr

Sama konstrukcja z „do” tłumaczy się do zwykłych wyrażeń Haskella za pomocą następujących reguł:

  • do { r }, gdzie r jest wyrażeniem odpowiedniego typu we-wy, tłumaczy się po prostu jako r,
  • do { x<-p; C; r }, gdzie C jest ciągiem poleceń, tłumaczy się jako p >>= q where q x = do { C; r }.

W tym drugim przypadku wyróżniliśmy osobno wyrażenie r, gdyż jego typ jest zarazem typem całego wyrażenia „do”. Ponadto jeśli p jest typu IO a, to x jest typu a. W szczególnym przypadku typu pustego (), zamiast x<-p pisze się po prostu p.

Podajmy jeszcze przykład kompletnego „programu interaktywnego”, wykorzystującego monadę we-wy. Zauważmy, że tego rodzaju program będzie miał zazwyczaj sygnaturę IO (), czyli będzie to funkcja bezparametrowa z wynikiem typu IO (). Przykładowy programik prosi o wprowadzenie napisu i sprawdza, czy jest to palindrom.

 programik :: IO ()
 programik = do putStr "Wprowadź napis: "
                cs <- getLine
                if palindrom cs
                   then putStrLn "Tak"
                   else putStrLn "Nie"
 
 palindrom :: String -> Bool
 palindrom x = (x == reverse x)

Mówiliśmy tu o monadach tylko w kontekście operacji we-wy, jednakże ich zastosowanie jest szersze. W ogólności monadą nazywa się instancję klasy Monad, a zatem typ, w którym istnieją operacje >>= i return. Monady są przydatne tam, gdzie potrzebne jest przechowanie stanu i narzucenie konkretnej kolejności obliczeń. Przytoczmy najistotniejszy fragment definicji klasy Monad; zauważmy, że w klasie tej parametr m oznacza nie typ, lecz konstruktor typu.

 class Monad m where
   return :: a -> m a
   (>>=)  :: m a -> (a -> m b) -> m b