Jak zaimplementować w Haskellu funkcję, obliczającą silnię? Każdy, kto chociaż zetknął się z tym językiem, będzie na pewno wiedział, że do gry powinna wkroczyć rekurencja. Chcąc wyliczyć n! dla n>0 będziemy liczyć n * (n-1)!, a warunkiem kończącym naszą rekurencję będzie zwrócenie wartości 1 dla 0!. Wielu początkujących ma jednak problem z tym, której konstrukcji Haskella należy użyć, do sprawdzenia owego warunku. Zwykłych ifów? A może case’a lub pattern matchingu? W tym artykule przyjrzę się dostępnym sposobom i spróbuję rozjaśnić kiedy najlepiej sprawdzają się poszczególne z nich.
Spis treści
1. Wyrażenie warunkowe
|
1 2 3 |
factorial n = if n == 0 then 1 else n * factorial(n-1) |
Ta składnia jest zdecydowanie najbliższa dla programistów, przybywających ze świata obiektowości. Podobno kod moglibyśmy napisać w wielu innych językach, a jego znaczenie jest dla wszystkich oczywiste. Tymczasem w Haskellu wyrażenie warunkowe ma grono swoich przeciwników, którzy postulują na przykład zastąpienie jej przez wprowadzenie zwykłej funkcji [1]:
|
1 2 |
if True x _ = x if False _ y = y |
Oczywiście teraz też każdy może sobie taką funkcję napisać i z niej korzystać, z tym że musi nazwać ją inaczej niż if (np. if'). Argumentów za funkcją zamiast lukru składniowego jest kilka, spośród których wspomnieć można to, że język zyskuje na spójności, a funkcji można użyć jako argumentu innych funkcji (przykłady zastosowań można znaleźć tutaj). Warto jeszcze wspomnieć o dwóch „dziwnościach” haskellowej instrukcji warunkowej:
- if zawsze występuje w parze z else, a zatem nie możemy po prostu go pominąć i napisać np.:
if debug then (putStrLn "Important message")ponieważ napotkamy błąd kompilatora. Zamiast tego powinniśmy użyć wszystkich elementów instrukcji warunkowej lub skorzystać z funkcjiwhenzdefiniowanej w moduleControl.Monad:
1234if debug then (putStrLn "Important message") else return()import Control.Monadwhen debug (putStrLn "Important message") - Bezpośrednio po if lub else nie można umieścić więcej niż jednej instrukcji. Aby to uczynić, należy użyć słowa kluczowego
do. Poniższy kod nie skomplikowałby się gdyby zabrakło w nim tego jednego krótkiego wyrazu:
123456if (success)then dosetMessage "OK"putStrLn "Success!"elseputStrLn "Failure :("
2. Guards
|
1 2 3 |
factorial n | n == 0 = 1 | otherwise = n * factorial (n-1) |
Chcąc używać wyrażeń których rezultatem jest wartość logiczna, możemy też poprosić o pomoc wartowników (ang. guards). Zasada jest prosta – fragment pomiędzy znakiem pionowej kreski (halabardą wartownika) a pojedynczym znakiem = musi ewaluować do True lub False.
Rolę else pełni na załączonym przykładzie słówko otherwise (w gruncie rzeczy będące tożsame ze zwykłym True), które przechwytuje wszystkie nie obsłużone wcześniej przypadki.
3. Case
|
1 2 |
factorial n = case n of 0 -> 1 n -> n * factorial (n-1) |
Tu nareszcie robi się ciekawiej! Może akurat nie w trywialnie prostym kodzie z silnią (choć i tu widać np. pozbycie się jawnych porównań z użyciem ==), ale w ogólności haskellowy case otwiera przed nami świat pattern matchingu, czyli, mówiąc po polsku, dopasowywania do wzorców.
Przestajemy ograniczać się do prymitywnych Booli i możemy rozpocząć zabawę z dekonstruowaniem danych. To własnie dzięki tej funkcjonalności Haskella możemy w prosty sposób rozłożyć listę na głowę i ogon (lub np. N pierwszych elementów i ogon) lub sprawdzić czy w zmiennej typu Maybe kryje się Nothing czy też jakaś konkretna wartość.
Przykład funkcji wykorzystującej dopasowywanie do wzorca znajduje się w ostatnim akapicie, natomiast w tym miejscu chciałbym jeszcze tylko zwrócić uwagę na drobny aspekt techniczny związany ze sposobem zapisu case w edytorze – wcięcia mają znaczenie i każde z dopasowań musi znajdować się na tym samym poziomie co wcześniejsze.
4. Dopasowywanie do wzorca w parametrach funkcji
|
1 2 |
factorial 0 = 1 factorial n = n * factorial (n-1) |
Samo dopasowywanie do wzorca działa tu identycznie jak w konstrukcji z użyciem case, a więc dysponujemy tą samą wolnością co i tam. Jedyna różnica jest taka, że odbywa się ono bezpośrednio na parametrach funkcji, a nie w dowolnym innym miejscu kodu. Osobiście uważam, że ten sposób implementacji silni jest najczytelniejszy ze względu na jej wierność matematycznej definicji.
Ważną kwestią, o której należy pamiętać (podobnie zresztą jak i w przypadku case) jest fakt, że kolejność wzorców może mieć niebagatelne znaczenie, ponieważ argument zostanie dopasowany do pierwszego wzorca, z którym będzie się zgadzał. Gdybyśmy zatem w podanej tu implementacji silni zamienili ze sobą obie linijki, nic dobrego by z tego nie wyszło.
5. Niejawna rekurencja
|
1 |
factorial n = product [1..n] |
Na koniec sposób, który z pewnością urzeka swoją prostotą i który w haskellowej wiki określony jest jako doskonały [2]. Funkcja product zwraca po prostu iloczyn elementów znajdujących się na liście przekazanej w argumencie (czyli robi to samo co foldl (*) 1). Jak podkreślają autorzy wspomnianej wiki, jawna rekurencja nie jest z zasady zła, ale nierzadko czytelniejsze rozwiązanie można uzyskać stosując zamiast niej funkcje wyższego rzędu.
Dużo lukru, czyli wszystko sprowadza się do case
Jeśli liczba dostępnych rozwiązań wydaje Ci się przytłaczająca, to dobra wiadomość jest taka, że wiele z nich to tylko tzw. lukier składniowy. Oznacza to, że niezależnie czy zaimplementujesz swoje rozwiązanie np. przy użyciu pattern matchingu w argumentach funkcji czy skorzystasz z konstrukcji case, to kod, jaki się wykona po skompilowaniu będzie bardzo podobny, a wydajność identyczna [3].
Jakie więc są owe lukrowe zależności? Na pewno guards to tylko przykrywka dla if-then-else, a dopasowywanie wzorca w argumentach funkcji jest cukrem składniowym, prowadzącym w rezutlacie do case. Dodatkowo, według niektórych źródeł, sama instrukcja warunkowa jest przez Haskella tłumaczona również do case [4].
Rule of thumb
Której ze składni należy więc używać? Niektórzy twierdzą, że dobrą zasadą dla początkujących jest, aby zawsze spróbować zaimplementować swoje rozwiązanie, korzystając z dopasowywania do wzorca. Rzeczywiście, tam gdzie ma to sens, warto preferować tę funkcjonalność, aniżeli wyrażenia warunkowe lub wartowników.
Z kolei tam, gdzie w oczywisty sposób porównujemy jakieś wartości i używanie wzorców ewidentnie nie ma sensu (np. sprawdzamy która z liczb jest większa), dobrze jest sięgnąć po konstrukcję guards.
Trzeba też mieć na uwadze fakt, że wydajność programu może się różnić w zależności od zastosowanych rozwiązań, nawet jeśli pozornie robią one dokładnie to samo. Jeden z użytkowników StackOverflow podaje przykład sprawdzania czy lista jest pusta [4]:
|
1 2 |
isEmpty xs = length xs == 0 -- pierwszy sposób isEmpty xs = case xs of { [] -> True; _:_ -> False } -- drugi sposób |
Pierwszy ze sposobów działa w czasie proporcjonalnym do długości listy xs, zaś koszt drugiej funkcji jest stały. Można to prosto zweryfikować, wywołując dla obu implementacji np. isEmpty [1..99999999].
Pattern guards, czyli wzorcowy koktajl
Na zakończenie zaprezentuję jeszcze jedną ciekawą funkcjonalność, wprowadzoną do Haskella w 2010 roku [5]. Są to tzw. pattern guards, które umożliwiają łączenie zwykłych porównań (pamiętajmy, że normalne guards muszą zwracać wartość logiczną) z dopasowywaniem do wzorca.
Składnia owej konstrukcji podobna jest do tej obecnej w list comprehensions (w których również możemy używać pattern matchingu, jak pokazano poniżej), zawierającej znak pionowej kreski, nazwę zmiennej oraz strzałkę w lewą stronę, np.:
|
1 2 3 |
[h | (h:t) <- [[1,2], [4,2,4], [5,6]], h == last t] [x | Just x <- [Just 5, Nothing, Just 10]] [x | [x] <- [[], [], [12], [1,2], [50]]] |
Gdybyśmy zatem chcieli zaimplementować funkcję, która będzie:
- dla pustej listy – zwracała liczbę 42
- dla jednoelementowej listy, której element jest większy niż 10 – zwracała wartość tego elementu
- dla jednoelementowej listy, której jest element jest mniejszy lub równy od 10 – zwracała wartość tego elementu pomniejszoną o 1
- dla dwuelementowej listy – zwracała iloczyn elementów
- dla listy posiadającej więcej niż dwa elementy – zwracała sumę pierwszego i ostatniego elementu
To w czytelny sposób możemy ją w Haskellu zapisać zarówno przy użyciu zwykłego pattern matchingu, jak i właśne pattern guards:
|
1 2 3 4 5 6 7 8 9 10 11 |
f [] = 42 f [a] = if a > 10 then a else a-1 f [a, b] = a * b f (h:t) = h + last t f x | [] <- x = 42 | [a] <- x, a > 10 = a | [a] <- x, a <= 10 = a-1 | [a, b] <- x = a * b | (h:t) <- x = h + last t |
Linki i źródła
- Haskell Wiki: if-then-else.
- Haskell Wiki: Haskell programming tips.
- Learn You a Haskell for Great Good!, Syntax in Functions.
- StackOverflow: Control statements in Haskell?
- StackOverflow: Pattern-Matching mixed with guards.
