haskell programowanie funkcyjne

Haskell i programowanie funkcyjne

Tematem mojego kolejnego wpisu o mniej znanych językach programowania jest Haskell i stojący za nim paradygmat, czyli programowanie funkcyjne. Jeżeli język Rust, o którym pisałem poprzednio  – wydał Ci się dziwny to poczekaj aż spróbujesz zmierzyć się właśnie z Haskellem. Programowanie w tym języku bardzo mocno odbiega od tego do czego przyzwyczajona jest większość programistów.

Czym jest programowanie funkcyjne?

W swojej znakomitej książce pt. „Czysta architektura” Robert Martin wymienia trzy tzw. paradygmaty programowania, które jego zdaniem nie zostawiają już miejsca na żadne inne. Są to: programowanie strukturalne (znane np. z języka C), programowanie obiektowe (C++, C#, Java i wiele innych) oraz właśnie programowanie funkcyjne. O ile wszyscy znają pierwsze dwa z tych paradygmatów, to programowanie funkcyjne dopiero od niedawna zaczęło się przebijać do „mainstreamu”. Co ciekawe sama idea programowania funkcyjnego jest starsza nawet niż komputery i swoimi korzeniami sięga do prac matematyków z lat 30 XX wieku.

Trudno jest wytłumaczyć czym jest programowanie funkcyjne bez konkretnych przykładów (jeszcze do nich dojdziemy). Główną ideą jest opisanie programu komputerowego jako złożenia funkcji, które w taki czy inny sposób transformują dane. Odróżnia to programowanie funkcje od programowania strukturalnego, w którym program opisuje się jako kolejno wykonywane przez procesor instrukcje.

Bez wnikania w szczegóły wyobraźmy sobie algorytm obliczania silnii opisany w sposób strukturalny i w sposób funkcyjny. Użyje tutaj pseudokodu, żeby nie przywiązywać się do konkretnego języka programowania:

 

//Silnia zdefiniowana w sposób strukturalny:
factorial(x):
y <- 1
for n in 1 to x:
  y <- y*x
return y
//Silnia zdefiniowana w sposób funkcjny
factorial(x) = 1 for x==0
factorial(x) = x*factorial(x-1) for x>0
  

Jak widzisz definicja w stylu funkcyjnym opiera się o rekurencję. Nie jest to przypadek – w programowaniu funkcyjnym rekurencje pojawiają się zdecydowanie częściej niż w innych paradygmatach. Nie myśl jednak, że programowanie funkcyjne to to samo co programowanie rekurencyjne. Pod tym pierwszym pojęciem kryje się dużo więcej.

Haskell i jego historia

Jak już wspomniałem, koncepcja programowania funkcyjnego jest starsza niż komputery. Również Haskell nie jest językiem nowym. Jego pierwszy szkic pojawił się już w roku 1990. Przez długi czas był to jednak język ograniczony do środowisk akademickich. Jego popularność zaczęła rosnąć stosunkowo niedawno. Nakłada się to zresztą na ogólnie rosnącą świadomość dotyczącą technik programowania funkcyjnego, którego elementy można znaleźć już właściwie w każdym z tzw. „mainstreamowych” języków (znajdziesz je m.in. w Javie, C#, JavaScripcie, Pythonie, a nawet w C++).

Język nazwano na cześć znanego logika Haskella Curry. Ideą przyświecającą jego utworzeniu było opracowanie jednego wspólnego języka opartego o programowanie funkcyjne i leniwą ewaluację. O programowaniu funkcyjnym trochę już pisałem, zaś do leniwej ewaluacji jeszcze wrócimy.

Obecnie Haskell może się pochwalić produkcyjnymi zastosowaniami w wielu firmach. Listę takich firm możesz znaleść np. na wiki Haskella. Jednym z głośniejszych zastosowań jest system antyspamowy Facebooka.

Skąd wziąć kompilator Haskella?

Jeżeli chcesz samodzielnie rozpocząć przygodę z Haskellem to najlepiej zacząć od ściągnięca pakietu narzędzi Haskell Platform. Najważniejsze z nich to oczywiście kompilator Haskella o nazwie GHC. Do tego przyda się jakieś IDE. Ja jak wiele razy pisałem preferuję Visual Studio Code z odpowiednią wtyczką.

Zacznijmy oczywiście od programu Hello, world!. Tworzymy plik hello.hs i wpisujemy tam następującą linijkę:

main = putStrLn "Hello, world!"
  

Całość kompilujemy poleceniem: ghc hello.hs i możemy uruchomić gotowy program.

Ciekawym narzędziem jest interaktywne środowisko Haskella o nazwie GHCI. Instaluje się ono razem z pakietem Haskell Platform i służy do interaktywnego uruchamiania kodu. Przypomina to bardzo korzystanie z interaktywnych sesji Pythona czy Node.js.

Uruchamiając środowisko GHCI możemy szybko wykonać nasz przykład z definiowaniem silnii. Po rozpoczęciu sesji wpisujemy (tekst Prelude> jest wyświetlany przez GHCI – nie wpisuj go):

Prelude> factorial x = if x==0 then 1 else x*factorial(x-1)           
Prelude> factorial(5)
120		

Jak widzisz bardzo przypomina to definicję w pseudokodzie, którą zapisałem wcześniej.

Zmienne w Haskellu

Języki funkcyjne bardzo duży nacisk kładą na niezmienniczość danych. Stąd w Haskellu zmienne nie odpowiadają, tak jak w „klasycznym” programowaniu, obszarom pamięci zawierającym jakieś dane, ale raczej wyrażeniom. Jeżeli utworzymy np. plik test.hs z następującym kodem:

x = 10

to będziemy mogli np. w GHCI załadować plik test.hs i odczytać wartość x. Odpowiednia sesja wygląda następująco:

 

Prelude> :l test.hs
[1 of 1] Compiling Main             ( test.hs, interpreted )
Ok, one module loaded.
*Main> x
10 

Jeżeli jednak spróbujemy przypisać coś do zmiennej x dwukrotnie:

x = 10
x = 11

to próba kompilacji zakończy się błędem:

Prelude> :l test.hs
[1 of 1] Compiling Main             ( test.hs, interpreted )

test.hs:2:1: error:
    Multiple declarations of `x'
    Declared at: test.hs:1:1
                 test.hs:2:1
  |
2 | x = 11
  | ^
Failed, no modules loaded.

Leniwa ewaluacja

Haskell bazuje na tzw. leniwej ewaluacji. Nie ma tu miejsca, żeby szczegółowo rozpisywać się na temat tej techniki. W skrócie chodzi o to, że wartości wyrażeń są obliczane dopiero wtedy kiedy są naprawdę potrzebne. Metoda ta stosowana we właściwy sposób pozwala na poprawę wydajności pisanych programów.

Oprócz tego zastosowanie leniwej ewaluacji umożliwi np. deklarowanie nieskończenie długich list. Spójrzmy na poniższy kod:

Prelude> x = [1..]                       
Prelude> take 10 x
[1,2,3,4,5,6,7,8,9,10]

Pierwsza linijka deklaruje listę zawierającą liczby całkowite od 1 do nieskończoności. Nieskończony rozmiar listy nie jest problemem, gdyż jej elementy będą obliczane dopiero wtedy gdy ktoś o nie zapyta. Dzieje się to np. w drugiej linijce, w której funkcja take pobiera pierwsze 10 elementów z listy x.

Inny ciekawy przykład możemy wykonać definiując następującą funkcję:

 

Prelude> expand x = [x] ++ expand (x+1)

Funkcja expand pobiera jeden argument (nawiasem mówiąc wszystkie funkcje w Haskellu pobierają jeden argument) i w efekcie buduje listę. Pierwszy element listy to argument podany do funkcji (instrukcja [x]). Jest on następnie składany (operator ++) z wynikiem działania funkcji expand dla argumentu x+1. 

W efekcie wywołanie tej funkcji dla dowolnej liczby spowoduje nieskończoną rekurencję. Ponownie nie jest to problemem, gdyż dzięki leniwej ewaluacji kolejne wywołania będą obliczane tylko wtedy kiedy będą potrzebne. Możemy np. znowu posłużyć się funkcją take:

Prelude> take 10 (expand 1)
[1,2,3,4,5,6,7,8,9,10]

FizzBuzz w Haskellu

Zobaczmy jak w stylu funkcyjnym można napisać program rozwiązujący zadanie FizzBuzz (o samym zadaniu pisałem jakiś czas temu). Odpowiedni kod jest następujący:

 

fizzbuzz :: Int -> String
fizzbuzz x | mod x 15 == 0 = "FizzBuzz"
           | mod x 3 == 0 = "Fizz"
           | mod x 5 == 0 = "Buzz"
           | otherwise = show x

main = mapM_ putStrLn $ take 10 (map fizzbuzz [1..])

Quicksort w stylu programowania funkcyjnego

Innym klasycznym przykładem algorytmu, na którym uczy się idei programowania funkcyjnego jest quicksort (znowu rekurencja). Idea jest bardzo prosta. Algorytm quicksort wybiera jeden z elementów listy, następnie umieszcza wszystkie elementy większe od niego po prawej stronie, mniejsze po lewej, a potem sortuje rekurencyjnie tak utworzone podlisty. W Haskellu odpowiednia implementacja jest następująca:

qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x:xs) = 
    let left  = qsort [a | a <-xs, a <= x]
        right = qsort [a | a <-xs, a >  x]
    in left ++ [x] ++ right

Bez sensu byłoby tutaj tłumaczyć Ci dokładnie działanie tej funkcji. Zwróc tylko uwagę na to, że kod jest napisany w sposób deklaratywny. Nie ma tutaj żadnych pętli czy serii wykonywanych po sobie instrukcji, a tylko składanie wyników różnych funkcji.

Podsumowanie

Języki oparte o czyste programowanie funkcyjne, a wśród nich i Haskell są mało popularne (chociaż udało mi się znaleźć kilka wymieniających ten język ofert pracy w Polsce) to warto znać ten paradygmat programowania. Jak już wspomniałem różne jego elementy wspierane są obecnie także przez inne, bardziej popularne języki.

Jeżeli masz ochotę dowiedzieć się więcej o programowaniu funkcyjnym to polecam wystąpienie Richarda Feldmana o tym dlaczego jego zdaniem ten paradygmat nie cieszy się popularnością:

Maciej Kraszewski

Maciej Kraszewski

Inżynier, menedżer R&D i nauczyciel akademicki. Uwielbiam zajmować się tworzeniem nowych technologii, zdobywaniem nowej wiedzy i dzieleniem się swoim doświadczeniem z innymi. Specjalizuję się w zagadnieniach przetwarzania obrazu i widzenia maszynowego.
Szukasz dobrych materiałów o projektowaniu elektroniki?

Załóż darmowe konto na naszej platformie i odbierz pakiet materiałów edukacyjnych.

Zakładając konto zgadzasz się na przesyłanie Ci treści marketingowych przez IT20 sp. z o.o. zgodnie z dostępną na stronie Polityką Prywatności. Możesz wycofać zgodę w każdej chwili.

2 komentarze do “Haskell i programowanie funkcyjne

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *

Szukasz dobrych materiałów o projektowaniu elektroniki?

Załóż darmowe konto na naszej platformie i odbierz pakiet materiałów edukacyjnych.

Zakładając konto zgadzasz się na przesyłanie Ci treści marketingowych przez IT20 sp. z o.o. zgodnie z dostępną na stronie Polityką Prywatności. Możesz wycofać zgodę w każdej chwili.

Zapisz się na listę mailową i odbierz swoje bonusy!

Więcej treści na temat elektroniki i robotyki, darmowe e-booki i dostęp do minikursów on-line. Otrzymasz to wszystko zapisując się na naszą listę mailową.