Programowanie funkcyjne w Pythonie

W komentarzu do poprzedniego wpisu nintyfan napisał:

O wcięciach w kodzie już było, więc teraz napiszę nieco o generatorach, iteratorach i programowaniu funkcyjnym. Zapraszam do czytania;)

Wstęp

Język Python można wykorzystać do programowania proceduralnego, zorientowanego obiektowo oraz (w mniejszym stopniu) programowania w stylu funkcyjnym (funkcjonalnym). Największą rolę odgrywa styl obiektowy, chociaż coraz częściej spotykam ciekawe rozwiązania napisane w stylu funkcyjnym. Nic w tym dziwnego. Programowanie funkcyjne pozwala w znaczny sposób zredukować ilość kodu.

Języki takie jak C, C++, Java to języki imperatywne. Programy w nich napisane zawierają zmienne i obiekty, na których przeprowadzane są operacje. Zmienne i obiekty charakteryzują się stanem, którym może ulegać zmianie w czasie wykonywania programu. Programy imperatywne stanowią listę rozkazów dla komputera.

Czym wyróżnia się paradygmat funkcyjny?

Nazwa programowanie funkcyjne pochodzi od funkcji (w ich matematycznym znaczeniu), na których dokonywane są ,,bezstanowe'' operacje. W programowaniu funkcyjnym definiujemy co trzeba wykonać, a nie w jaki sposób.

Niektóre cechy/elementy języków czysto funkcyjnych (na przykładzie Haskella ) [1] to:

* Funkcje to pojęcia podstawowe (ang. first-class) * Funkcje mogą operować na funkcjach (ang. high-order functions) * Rekurencja zamiast pętli * Listy jako podstawowa struktura danych * Brak efektów ubocznych (ang. no side-effect) * Wyrażenia lambda (funkcje anonimowe) * Leniwe wartościowanie (ang. lazy evaluation) * Strażnicy (ang. guards)

Po czym najłatwiej rozpoznać, że mamy do czynienia z językiem funkcyjnym? Po wymienionych powyżej funkcjach lambda i pewnych podstawowych funkcjach (ang. primary functional programming primitives) takich jak: map, filter, reduce, fold, scan. Używanie tych funkcji najczęściej prowadzi do eliminacji pętli.

Python językiem funkcyjnym nie jest, a już na pewno nie jest językiem czysto funkcyjnym, ale posiada pewne cechy charaketrystyczne dla tych języków. Przede wszystkim umożliwia korzystanie z wyrażeń lambda oraz dostarcza wymienione powyżej funkcje map, filter, reduce.

Równie ważne są iteratory oraz generatory dostępne w modułach biblioteki standardowej takich jak itertools i functools.

Mapowanie polega na pobieraniu funkcji oraz obiektu pozwalającego na iterację i wygenerowanie nowego elementy iterowanego, w którym element będzie wynikiem wywołania funkcji względem odpowiadającego mu elementu w początkowym obiekcie [3].

Filtrowanie pozwala na iterację i wygenerowanie nowego iteratora, w którym każdy element pochodzi z początkowego iteratora--pod warunkiem, że funkcja wywołana względem tego iteratora zwróciła wartość True [3].

Redukcja natomiast polega na pobieraniu funkcji i obiektu pozwalającego na iterację, a następnie wygenerowaniu pojedynczej wartości [3], np.

functools.reduce(lambda x, y: x * y, [1, 2, 3, 4]) # wynik: 24

Przyjrzyjmy się bliżej wyrażeniom lambda. Przeanalizujmy następujący przykład:

>>> def f(x): return x ** 2

>>> f(4)
16

To samo można zrealizować przy pomocy funkcji anonimowej.

>>> g = lambda x : x ** 2
>>> g(4)
16

Nie musimy nawet używać nazwy argumentu. Czasami po prostu chcemy obliczyć wartość funkcji od ,,czegoś'', czymkolwiek to ,,coś'' jest.

>>> h = lambda _ : _ ** 2
>>> h(4)
16

Wyobraźmy sobie następujący problem:

Poszukujemy kwadratów liczb naturalnych od 1 do 10, o wartościach większych od 50.

Powyższy problem można rozwiązać w Haskellu w następujący sposób:

> filter (>50) (map (**2) [1..10])
[64.0,81.0,100.0]

W Pythonie można skorzystać np. z pętli for, polecenia if oraz append:

lub zrealizować to w sposób funkcyjny w jednej linii bez wprowadzania nowych zmiennych i funkcji:

>>> list(filter(lambda _ : _ > 50, map(lambda _ : _ ** 2, range(11))))
[64, 81, 100]

Inną charakterystyczną cechą Haskella jest leniwość. Zaletami tego podejścia są możliwość obliczenia wartości funkcji nawet wtedy, gdy nie jest możliwe wyznaczenie wartości któregoś z jej argumentów, o ile tylko nie jest on używany, wzrost wydajności dzięki uniknięciu wykonywania niepotrzebnych obliczeń oraz możliwość tworzenia nieskończonych struktur danych.

Spójrzmy na jeszcze jeden przykład napisany w Haskellu:

ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))  
166650  

Lista [1..] to lista nieskończona. Może wydawać się to dziwne dla osób, które po raz pierwszy się spotykają z taką strukturą. Przecież program nie może działać w nieskończoność. To prawda, ale na etapie programowania jest to bardzo wygodne. Definiujemy nieskończoną listę elementów, a później przy pomocy funkcji take lub takeWhile bierzemy tyle ile nam potrzeba.

W Pythonie podobną listę można zrealizować przy pomocy generatorów. Generatory wykonują rodzaj leniwych obliczeń, tzn. obliczają jedynie te wartości, które są potrzebne w danej chwili [3].

Przykład:

Polecenie break jest tutaj konieczne -- bez niego pętla for..in nigdy nie zakończy działania.

Moduł Pipe

W podsumowaniu powyższych rozważań przedstawię krótko bardzo ciekawy moduł Pipe.

Głównym zadaniem modułu jest umożliwienie stosowania składni ,,infix''. Funkcje typu ,,infix'' zapisujemy podobnie jak podstawowe operacje dodawania, mnożenia itd. Np.:

plus a b = a + b
plus 1 5 == 1 `plus` 5

W module tym zaimplementowane są przy pomocy generatorów podstawowe funkcje znane z Haskella takie jak: where(), take(), take_while(), tail(), groupby(), reverse(), permutations() etc.

Oto kilka prostych przykładów zastosowań:

>>> from pipe import *
>>> [1, 2, 3, 4, 5] | add
15
>>> [5, 4, 3, 2, 1] | sort
[1, 2, 3, 4, 5]

>>> [1, 2, 3, 4, 5] | where(lambda x: x % 2) | concat
'1, 3, 5'
>>> [1, 2, 3, 4, 5] | where(lambda x: x % 2) | tail(2) | concat
'3, 5'
>>> [1, 2, 3, 4, 5] | where(lambda x: x % 2) | tail(2) | select(lambda x: x * x) | concat
'9, 25'
>>> [1, 2, 3, 4, 5] | where(lambda x: x % 2) | tail(2) | select(lambda x: x * x) | add
34

Na koniec nieco bardziej zaawansowany przykład zastosowania klasycznego ciągu Fibonacciego:

euler2 = fib() | where(lambda x: x % 2 == 0) | take_while(lambda x: x < 4000000) | add

Warto przeczytać:

* Why Functional Programming Matters, John Hughes * Learn You a Haskell for Great Good!, Miran Lipovaca

Źródła:

1. Programowanie funkcyjne w Pythonie, Adam Byrtek 2. Functional Programming HOWTO, Python 3 documentation 3. Python 3. Kompletne wprowadzenie do programowania. Wydanie II, Mark Summerfield