Programowanie funkcjonalne - inne spojrzenie na świat

31.10.2009 - Krzysztof Skrzętnicki
TrudnośćTrudność

Do czego to wszystko prowadzi?

Na początku artykułu padło stwierdzenie, że programowanie funkcjonalne pozwala wyrażać skomplikowane algorytmy w prostszy sposób, niż ma to miejsce dla tradycyjnych, imperatywnych języków. Przekonajmy się naocznie, że jest tak faktycznie.

Jednym z powszechnie znanych algorytmów sortujących jest Quicksort. Jego ideę można wyrazić bardzo prosto:

  1. Wybieramy z listy pewien element dzielący X.
  2. Dzielimy elementy na mniejsze i większe od X.
  3. Obie części sortujemy rekurencyjnie i zwracamy razem z elementem X.

Ten opis przepisuje się niemal jeden-do-jeden na kod Haskella. Z tą różnicą, że kod jest krótszy niż opis:

1
2
3
4
quicksort [] = [] -- lista pusta jest posortowana
quicksort (x:xs) = quicksort (filter (<x) xs) ++ -- sortujemy elementy mniejsze
                   [x] ++                        -- element dzielący
                   quicksort (filter (>x) xs)    -- sortujemy elementy większe

W przypadku bazowym sortujemy listę pustą - która jest już posortowana, więc zwracamy listę pustą. Jeżeli lista nie jest pusta, to wybieramy pierwszy jej element jako element dzielący (zwany pivotem). Sortujemy rekurencyjnie elementy mniejsze od x:

1
quicksort (filter (<x) xs)

Większe od x:

1
quicksort (filter (>x) xs)

Następnie łączymy wszystkie części operatorem łączenia list ++. I gotowe!


Operator ++ służy do łączenia list. Można go prosto zdefiniować:
1
2
[] ++ xs = xs
(y:ys) ++ xs = y : (ys ++ xs)

Dla porównania poniżej przykładowa, imperatywna implementacja algorytmu Quicksort w Pythonie (częściowo zapożyczona z Wikipedii). Na pierwszy rzut oka widać o ile dłuższy jest to kod. Podobny kod napisany w C byłby jeszcze bardziej rozciągnięty.

1
2
3
4
5
6
7
8
9
10
11
12
def quicksort(arr, l=0, r=None):
    if r is None: r = len(arr) - 1
    i, j = l, r
    pivot = arr[0]
    while i <= j:
        while arr[i] < pivot: i += 1
        while arr[j] > pivot: j -= 1
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1; j -= 1
    if l < j: quicksort(arr, l, j) 
    if r > i: quicksort(arr, i, r) 

Wpisz kod poniżej, aby go uruchomić. Zobacz, jak quicksort sortuje różne listy, np. [5,1,7,2,3,4] albo "Haskell".


To już jest koniec...

Chociaż opowieść o Haskellu i programowaniu funkcjonalnym można snuć w nieskończoność, to tutaj musimy zakończyć. Mam nadzieję, że zdołał on przekonać Was o potędze tych wspaniałych narzędzi. Owocem koronnym naszej podróży była jasna i prosta definicja algorytmu, który bywa rozpisywany na kilkadziesiąt linii!

Jeżeli zaś nie, to liczę na to, że przynajmniej zaciekawił Was ten jakże odmienny język. W ostatnich latach wyraźnie wzmógł sie ruch wokół języków funkcjonalnych, stworzono też kilka nowych. Sam Haskell wspierany jest przez Microsoft, który jest też producentem innego języka funkcjonalnego - F#. Oba znajdują zastosowanie w wiodących firmach programistycznych na świecie.Zachęcam gorąco do studiowania programowania funkcjonalnego - choć paradygmat jest już stary, to jednak najlepsze jego lata dopiero nadchodzą!

3.5
Twoja ocena: Brak Ocena: 3.5 (6 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com