Próbka paradygmatu funkcjonalnego

12 grudnia 2009, dyskusja: 21 komentarzy

Najbardziej rozpowszechnionym paradygmatem programowania jest paradygmat imperatywny. W jego ujęciu program jest ciągiem instrukcji modyfikujących stan. Istnieją jednak inne podejścia, a jednym z nich jest paradygmat funkcjonalny, który traktuje program jak obliczenie wartości pewnej funkcji. Wybór paradygmatu ma ogromny wpływ zarówno na języki programowania jak i same programy, co postaramy się zademonstrować na prostym przykładzie.

Naszym zadaniem będzie rozwiązanie klasycznego problemu sumy podzbioru. Jest on zadany następująco: mając dany niepusty i skończony zbiór liczb należy znaleźć wszystkie jego podzbiory, których suma elementów jest zerowa (dla uproszczenia do rozwiązania dopuścimy zbiór pusty). Rozwiążemy go przy pomocy PHP i Haskella starając się, aby kod w PHP był jak najbliższy duchowi funkcjonalności.

Zaimplementujemy rozwiązanie, które podpowiada nam intuicja. Najpierw wybierzemy wszystkie podzbiory rozważanego zbioru, a następnie zostawimy tylko te, których suma jest zerowa. Opis ten jest truistyczny i bardzo ogólnikowy, jednak jest w zupełności wystarczający.

Zaczniemy od rozwiązania w PHP. Zbiór będziemy reprezentować przy pomocy tablicy. Do dyspozycji mamy funkcję sumującą elementy (array_sum) oraz filtrującą (array_filter), jednak nie ma funkcji zwracającej wszystkie podtablice. Musimy napisać ją samodzielnie.

  1. function subarrays($array)
  2. {
  3.   if(!$array)
  4.   {
  5.     return array(array());
  6.   }
  7.   $last = array_pop($array);
  8.   $subarrays = subarrays($array);
  9.   foreach($subarrays as $subarray)
  10.   {
  11.     $newsubarray = $subarray;
  12.     $newsubarray[] = $last;
  13.     $subarrays[] = $newsubarray;
  14.   }
  15.   return $subarrays;
  16. }
  17. function zero_sum($array)
  18. {
  19.   return !array_sum($array);
  20. }
  21. $input = array(-2, -1, 0, 1, 2);
  22. $output = array_filter(subarrays($input), 'zero_sum');
  23. print_r($output);

Rozwiązanie uzyskujemy w jednej linii, wykonując na tablicy wejściowej $input kilka elementarnych operacji. Dodatkowo od wersji 5.3 można użyć anonimowej funkcji jako filtru (pomijamy prowizoryczną funkcję create_function).

Spójrzmy jak sprawa wygląda w Haskellu. Tutaj do dyspozycji mamy cały arsenał funkcji i nie musimy niczego pisać samodzielnie.

  1. import Data.List
  2. main = do
  3.   putStrLn $ show output
  4.   where
  5.     input = [-2..2]
  6.     output = filter ((== 0) . sum) $ subsequences input

input jest wejściową listą. output jest konstruowany w banalny sposób: wybieramy wszystkie podlisty (funkcja subsequences), a następnie wybieramy te z zerową sumą (funkcja filter i filtr (== 0) . sum). Piękne!

Posługując się tym trywialnym przykładem pokazaliśmy jak stosowany paradygmat wpływa na składnię języka, sposób myślenia o problemach i wygląd programów. Funkcjonalność daje nam zwięzłość i łatwość zrozumienia, a także niebywałą estetykę. Dlatego warto wyjść poza nurt imperatywny, chociażby na próbę, aby zyskać nowe spojrzenie na programowanie. Niech do popularnych języków takich jak PHP, Python, Ruby czy Java dołączą Erlang, Haskell i Scala!

Atraktor Clifforda, czyli piękno matematyki

07 grudnia 2009, dyskusja: 4 komentarze

Matematyka, której zimne piękno niejednego przeraża, posiada też ogromny aspekt estetyczny. Nie chodzi tutaj o zmyślność dowodów czy rozumowań, ale o piękno wizualne. Zapewne największą popularnością cieszą się fraktale. W moim odczuciu równie piękne są atraktory.

Atraktor Clifforda jest określony przy pomocy elementarnych operacji matematycznych: dodawania, mnożenia oraz sinusa i cosinusa. Ta prostota przekłada się na czyste piękno. Przekonać się można o tym przy pomocy prostego generatora atraktorów. Program ten wysyła zadany atraktor, określony przez cztery współczynniki, w formacie PPM na standardowe wyjście. Do działania potrzebuje biblioteki netpbm.

W Internecie można znaleźć więcej informacji na temat atraktorów. Polecam skromną galerię atraktorów z której można wziąć przykładowe współczynniki. Kolejnym etapem może być wprawienie atraktora w ruch, czyli mała animacja, albo zwiększenie rozdzielczości. Zachęcam do eksperymentów!