02/05/2023
W świecie programowania funkcyjnego istnieją koncepcje, które, choć na pierwszy rzut oka mogą wydawać się abstrakcyjne, stanowią fundament eleganckiego i efektywnego kodu. Dwie z nich, ściśle ze sobą powiązane, to kurryzacja i unkurryzacja. Pochodzące z logiki matematycznej i teorii kategorii, te transformacje funkcji odgrywają kluczową rolę w językach takich jak Haskell, umożliwiając tworzenie bardziej modułowych, elastycznych i łatwiejszych do komponowania programów. W tym artykule zagłębimy się w naturę tych operacji, wyjaśnimy ich motywacje, różnice oraz pokażemy, jak są wykorzystywane w praktyce.
Co to jest Kurryzacja?
Kurryzacja (ang. currying) to proces przekształcania funkcji, która przyjmuje wiele argumentów, w sekwencję funkcji, z których każda przyjmuje tylko jeden argument. Nazwa pochodzi od logisty Hasana F. Curry'ego, choć podobne idee były już wcześniej badane przez Mosesa Schönfinkela i Gottloba Fregego.
Motywacje i Historia
Główną motywacją stojącą za kurryzacją jest możliwość pracy z funkcjami, które przyjmują wiele argumentów, w ramach systemów, gdzie funkcje mogą przyjmować tylko jeden argument. Na przykład, niektóre techniki analityczne mogą być stosowane wyłącznie do funkcji jednoargumentowych. Praktyczne funkcje często wymagają jednak wielu argumentów. Frege wykazał, że wystarczy znaleźć rozwiązania dla przypadku jednoargumentowego, ponieważ możliwe jest przekształcenie funkcji wieloargumentowej w łańcuch funkcji jednoargumentowych. To przekształcenie jest procesem znanym obecnie jako kurryzacja.
Wszystkie "zwykłe" funkcje, które typowo spotyka się w analizie matematycznej lub programowaniu, mogą być kurryzowane. Istnieją jednak kategorie, w których kurryzacja nie jest możliwa. Najbardziej ogólne kategorie, które pozwalają na kurryzację, to zamknięte kategorie monoidalne.
Niektóre języki programowania, takie jak ML i Haskell, niemal zawsze używają funkcji kurryzowanych do obsługi wielu argumentów. W obu tych językach wszystkie funkcje mają dokładnie jeden argument. Ta właściwość została odziedziczona z rachunku lambda, gdzie funkcje wieloargumentowe są zazwyczaj reprezentowane w formie kurryzowanej.
Jak działa Kurryzacja?
Wyobraźmy sobie prostą funkcję dodaj(a, b), która przyjmuje dwa argumenty i zwraca ich sumę. W wersji kurryzowanej, ta sama funkcja mogłaby wyglądać tak: dodajCurry(a)(b). Oznacza to, że po podaniu pierwszego argumentu a, funkcja zwraca nową funkcję, która oczekuje na drugi argument b. Dopiero po podaniu drugiego argumentu otrzymujemy końcowy wynik. Formalnie, jeśli mamy funkcję f: (X × Y × Z) → N (funkcję przyjmującą krotkę trzech argumentów i zwracającą wartość typu N), kurryzacja przekształca ją w curry(f): X → (Y → (Z → N)). Oznacza to, że wywołanie f(1, 2, 3) staje się f_curried(1)(2)(3), gdzie każdy argument jest stosowany po kolei do funkcji jednoargumentowej zwracanej przez poprzednie wywołanie.
Kurryzacja a Częściowe Stosowanie Funkcji
Kurryzacja i częściowe stosowanie funkcji (ang. partial application) są często mylone, ale są to odmienne koncepcje. Kluczowa różnica polega na tym, że wywołanie funkcji częściowo zastosowanej zwraca wynik od razu (lub funkcję o mniejszej arytmii), a nie kolejną funkcję w łańcuchu kurryzacji.
Różnice
Przyjrzyjmy się ponownie funkcji f: (X × Y × Z) → N. Jak już wspomniano, kurryzacja daje nam curry(f): X → (Y → (Z → N)). Po wywołaniu f_curried(1), otrzymujemy funkcję, która przyjmuje pojedynczy argument (typu Y) i zwraca kolejną funkcję. Nie jest to funkcja, która od razu przyjmuje dwa argumenty.
Z kolei częściowe stosowanie funkcji odnosi się do procesu "ustalania" pewnej liczby argumentów funkcji, co prowadzi do powstania nowej funkcji o mniejszej arytmii. Jeśli zdefiniujemy partial(f): (Y × Z) → N poprzez ustalenie pierwszego argumentu funkcji f, to wywołanie tej funkcji może być reprezentowane jako f_partial(2, 3). Zauważ, że wynik częściowego zastosowania w tym przypadku jest funkcją, która przyjmuje dwa argumenty, a nie jedną po drugiej.
Intuicyjnie, częściowe stosowanie funkcji mówi: "jeśli ustalisz pierwszy argument funkcji, otrzymasz funkcję pozostałych argumentów". Na przykład, jeśli funkcja div oznacza operację dzielenia x/y, to div z parametrem x ustalonym na 1 (czyli div 1) jest inną funkcją: taką samą jak funkcja inv, która zwraca odwrotność multiplikatywną swojego argumentu, zdefiniowana jako inv(y) = 1/y. Praktyczną motywacją dla częściowego stosowania jest to, że funkcje uzyskane przez podanie niektórych, ale nie wszystkich argumentów, są często przydatne. Na przykład, wiele języków ma funkcję lub operator podobny do plus_one. Częściowe stosowanie ułatwia definiowanie tych funkcji, na przykład poprzez stworzenie funkcji, która reprezentuje operator dodawania z 1 jako pierwszym argumentem.
Częściowe stosowanie może być postrzegane jako ewaluacja funkcji kurryzowanej w ustalonym punkcie. Zatem, częściowe stosowanie jest teoretycznie sprowadzalne do pojedynczej operacji kurryzacji na pewnej kolejności danych wejściowych funkcji. W związku z tym, kurryzacja jest bardziej odpowiednio definiowana jako operacja, która w wielu przypadkach teoretycznych jest często stosowana rekurencyjnie, ale która jest teoretycznie nierozróżnialna (gdy rozpatruje się ją jako operację) od częściowego stosowania.
| Cecha | Kurryzacja | Częściowe Stosowanie Funkcji |
|---|---|---|
| Definicja | Transformuje funkcję wieloargumentową w sekwencję funkcji jednoargumentowych, gdzie każda zwraca kolejną funkcję oczekującą na następny argument. | Ustalenie pewnej liczby początkowych argumentów funkcji, co tworzy nową funkcję z mniejszą liczbą pozostałych argumentów. |
| Typ zwracany | Zawsze zwraca nową funkcję, która oczekuje na kolejny argument, aż do podania wszystkich. | Zwraca funkcję o mniejszej arytmii (jeśli nie wszystkie argumenty zostały podane) lub końcowy wynik (jeśli wszystkie argumenty zostały podane). |
| Liczba argumentów | Zmienia sposób przyjmowania argumentów (jeden po drugim). | Zmniejsza "arytmię" funkcji (liczbę argumentów, które jeszcze trzeba podać). |
| Przykład | f(a,b,c) staje się f_curried(a)(b)(c) | f(a,b,c) po ustaleniu a staje się f_partial(b,c) |
| Zastosowanie | Fundament języków funkcyjnych (np. Haskell), budowanie potoków funkcji. | Tworzenie specjalizowanych wersji funkcji, ułatwienie kompozycji. |
Co robi Unkurryzacja?
Unkurryzacja (ang. uncurrying) to operacja odwrotna do kurryzacji. Polega na przekształceniu funkcji, która przyjmuje argumenty jeden po drugim (czyli funkcji kurryzowanej lub naturalnie kurryzowanej w językach takich jak Haskell), z powrotem w funkcję, która przyjmuje wszystkie swoje argumenty naraz, zazwyczaj w postaci krotki (ang. tuple) lub ścisłej pary (ang. strict pair).
Jeśli mamy funkcję f_curried: X → (Y → Z), unkurryzacja przekształci ją w uncurry(f_curried): (X, Y) → Z. Oznacza to, że zamiast wywoływać f_curried(x)(y), możemy wywołać uncurry(f_curried)((x, y)), przekazując parę argumentów.
W kontekście funkcji przyjmujących więcej niż dwa argumenty, unkurryzacja może przekształcić funkcję kurryzowaną w funkcję przyjmującą krotkę o odpowiedniej liczbie elementów. Na przykład, funkcja kurryzowana przyjmująca trzy argumenty X → (Y → (Z → N)) może być unkurryzowana do funkcji przyjmującej potrójną krotkę (X, Y, Z) → N.
Kurryzacja i Unkurryzacja w Haskellu
Haskell jest doskonałym przykładem języka, w którym funkcje są z natury kurryzowane. Oznacza to, że każda funkcja w Haskellu, która wydaje się przyjmować wiele argumentów, w rzeczywistości jest sekwencją funkcji jednoargumentowych. Na przykład, definicja funkcji add :: Int -> Int -> Int nie oznacza, że add przyjmuje dwa argumenty typu Int jednocześnie, ale że przyjmuje jeden Int i zwraca nową funkcję, która przyjmuje kolejny Int i dopiero wtedy zwraca wynik.
Standardowa biblioteka Haskella zawiera dwie przydatne funkcje: curry i uncurry, które ułatwiają konwersję między funkcjami, które przyjmują dwa argumenty (jeden po drugim, co jest standardem w Haskellu) a funkcjami, które przyjmują krotkę argumentów.
Funkcja curry w Haskellu
Funkcja curry przekształca funkcję, która przyjmuje krotkę argumentów (np. parę), w funkcję, która przyjmuje te argumenty jako oddzielne. Jej sygnatura typu dla funkcji dwuargumentowej to curry :: ((a, b) -> c) -> a -> b -> c. Przykład:
-- Funkcja przyjmująca krotkę uncurriedAddition :: (Int, Int) -> Int uncurriedAddition nums = let a = fst nums b = snd nums in a + b -- Użycie curry do przekształcenia jej w funkcję przyjmującą dwa oddzielne argumenty addition :: Int -> Int -> Int addition = curry uncurriedAddition -- Testowanie w GHCi: -- λ addition 1 2 -- 3 -- λ addOne = addition 1 -- λ addOne 5 -- 6 Jak widać, addition zachowuje się jak zwykła funkcja dwuargumentowa w Haskellu, mimo że jej bazą była funkcja przyjmująca krotkę. Pozwala to na łatwe tworzenie funkcji częściowo zastosowanych, takich jak addOne, poprzez podanie tylko pierwszego argumentu.
Funkcja uncurry w Haskellu
Funkcja uncurry działa w przeciwnym kierunku: bierze "zwykłą" funkcję haskellową (czyli już kurryzowaną) z dwoma argumentami i konwertuje ją na funkcję, która akceptuje pojedynczą krotkę (parę) tych argumentów. Jej sygnatura typu to uncurry :: (a -> b -> c) -> ((a, b) -> c). Przykład:
-- "Zwykła" funkcja dodawania w Haskellu (jest już kurryzowana) addNumbers :: Int -> Int -> Int addNumbers a b = a + b -- Użycie uncurry do przekształcenia jej w funkcję przyjmującą krotkę addTuple :: (Int, Int) -> Int addTuple = uncurry addNumbers -- Testowanie w GHCi: -- λ addTuple (1, 2) -- 3 -- λ addTuple (10, 20) -- 30 Warto zauważyć, że operator dodawania (+) w Haskellu to również funkcja kurryzowana. Możemy więc bezpośrednio użyć uncurry (+), aby uzyskać funkcję, która dodaje elementy z krotki:
uncurriedAdditionFromPlus :: (Int, Int) -> Int uncurriedAdditionFromPlus = uncurry (+) -- Testowanie w GHCi: -- λ uncurriedAdditionFromPlus (5, 7) -- 12 Implementacja własnych wersji curry i uncurry
Zrozumienie, jak działają curry i uncurry, jest kluczowe dla głębszego pojmowania programowania funkcyjnego. Można spróbować zaimplementować je samodzielnie, aby utrwalić wiedzę:
myCurry :: ((a, b) -> c) -> a -> b -> c myCurry f x y = f (x, y) myUncurry :: (a -> b -> c) -> ((a, b) -> c) myUncurry f (x, y) = f x y Te proste definicje pokazują esencję tych transformacji: myCurry bierze funkcję f, która oczekuje krotki (x, y), i zwraca nową funkcję, która przyjmuje x, a następnie y, ostatecznie przekazując je jako krotkę do oryginalnej funkcji f. Z kolei myUncurry bierze funkcję f, która oczekuje x, a następnie y, i zwraca nową funkcję, która przyjmuje krotkę (x, y), rozpakowując ją i przekazując poszczególne elementy do oryginalnej funkcji f.
Zalety i Zastosowania
Kurryzacja i unkurryzacja, choć mogą wydawać się niszowymi koncepcjami, mają fundamentalne znaczenie i przynoszą wiele korzyści w programowaniu funkcyjnym:
- Modułowość i Reużywalność: Funkcje kurryzowane są z natury bardziej modułowe. Można je częściowo aplikować, tworząc nowe, bardziej wyspecjalizowane funkcje z istniejących. To sprzyja reużywalności kodu.
- Łatwiejsza Kompozycja: Ponieważ funkcje kurryzowane przyjmują jeden argument i zwracają jedną wartość (która może być kolejną funkcją), idealnie nadają się do kompozycji funkcji. Wynik jednej funkcji może być bezpośrednio wejściem dla innej.
- Tworzenie Domenowych Języków (DSL): Dzięki kurryzacji i częściowemu stosowaniu można tworzyć bardzo czytelne i ekspresyjne "zdania" w kodzie, które przypominają język naturalny lub język specyficzny dla danej dziedziny.
- Wsparcie dla Rachunku Lambda: Kurryzacja jest fundamentalna dla rachunku lambda, na którym opiera się wiele języków funkcyjnych. Pozwala na reprezentowanie wszystkich funkcji w jednolitej formie jednoargumentowej.
- Elastyczność w Przekazywaniu Argumentów: Unkurryzacja pozwala na łatwą konwersję funkcji, gdy potrzebujemy przekazać argumenty w postaci pojedynczej struktury danych (np. krotki), co może być przydatne w kontekstach, gdzie API oczekuje pojedynczego obiektu wejściowego.
Często Zadawane Pytania (FAQ)
Czy kurryzacja jest tym samym co częściowe stosowanie funkcji?
Nie, choć są ze sobą powiązane i często mylone. Kurryzacja to transformacja funkcji, która zmienia jej strukturę tak, aby przyjmowała argumenty jeden po drugim, zwracając kolejną funkcję. Częściowe stosowanie funkcji to akt podania części argumentów funkcji (kurryzowanej lub nie), aby uzyskać nową funkcję o mniejszej liczbie pozostałych argumentów. Kurryzacja to technika, która ułatwia częściowe stosowanie.
Dlaczego Haskell używa kurryzacji?
Haskell jest językiem czysto funkcyjnym, opartym na rachunku lambda. W rachunku lambda wszystkie funkcje są z natury jednoargumentowe. Przyjęcie kurryzacji jako domyślnego sposobu obsługi wielu argumentów sprawia, że język jest bardziej spójny i elegancki, ułatwiając kompozycję funkcji i rozumowanie o programach.
Czy mogę unkurryzować funkcję z więcej niż dwoma argumentami?
Tak, funkcja uncurry w Haskellu jest typowo definiowana dla funkcji dwuargumentowych, przekształcając je w funkcje przyjmujące parę. Jednak koncepcja unkurryzacji jest ogólna i można stworzyć własne funkcje do unkurryzowania funkcji przyjmujących trzy, cztery lub więcej argumentów, przekształcając je w funkcje przyjmujące odpowiednio potrójne, poczwórne krotki itd.
Podsumowanie
Kurryzacja i unkurryzacja to potężne narzędzia w arsenale programisty funkcyjnego. Zrozumienie ich mechanizmów i różnic w stosunku do częściowego stosowania funkcji otwiera drzwi do pisania bardziej elastycznego, modułowego i czytelnego kodu, zwłaszcza w językach takich jak Haskell. Choć początkowo mogą wydawać się trudne do uchwycenia, ich opanowanie znacznie poszerza perspektywy w projektowaniu oprogramowania i pozwala na pełniejsze wykorzystanie paradygmatu funkcyjnego.
Zainteresował Cię artykuł Kurryzacja i Unkurryzacja: Przewodnik po Funkcjach? Zajrzyj też do kategorii Kulinaria, znajdziesz tam więcej podobnych treści!