Tym czytelnikom, którzy np. na studiach mieli do czynienia z kursem algebry, być może obiły się gdzieś o uszy takie pojęcia jak grupa, półgrupa oraz monoid. Jeśli jesteś jedną z takich osób, to możliwe też, że nigdy nie wykorzystałeś(aś) tej wiedzy poza murami uczelni i nieco uleciała Ci ona z głowy. Nic dziwnego, tego typu matematyczne abstrakcje nie pojawiają się w większości języków programowania. Co innego w Haskellu, który bardzo lubi się z wszelkimi algebraicznymi strukturami i matematyczną teorią.

Z matematycznej perspektywy

Grupoidy i półgrupy

Grupoid (inaczej magma) to zbiór z określonym na nim dowolnym wewnętrznym (tzn. takim, którego wynik jest elementem tego samego zbioru) działaniem dwuargumentowym. [1] I tyle. Żadnych innych ograniczeń. Jak pewnie się domyślasz, zalicza się tutaj cała masa różnego zbiorów, zaczynając chociażby od liczb całkowitych, naturalnych i rzeczywistych.

Gdy do struktury grupoidu dołożymy jedno małe ograniczenie wobec wspomnianego działania dwuargumentowego, będziemy mieli do czynienia z półgrupą. Ograniczeniem tym jest łączność. Działanie jest łączne wtedy, gdy umieszczenie nawiasów, a co za tym idzie kolejność wykonywania obliczeń, nie ma znaczenia i zawsze otrzymujemy ten sam wynik.

Np. przy dodawaniu: (a + b) + c = a + (b + c) oraz przy złożeniu funkcji f . (g . h) = (f . g) . h, ale już nie przy odejmowaniu: (a - b) - c != a - (b - c).

Monoidy

Kiedy z kolei wzbogacimy półgrupę o jeszcze jedną restrykcję, będziemy mogli wreszcie mówić o monoidzie. Tym dodatkowym ograniczeniem jest istnienie elementu neutralnego, który przyłożony do dowolnego innego elementu nie zmieni go. Na przykład:

• dla liczb naturalnych (z zerem) i operacji dodawania elementem neutralnym jest zero. Dla dowolnej liczby a, istnieje bowiem zależność a + 0 = 0 + a = a
• dla liczb naturalnych i operacji mnożenia element neutralny to jedynka, ponieważ: a * 1 = 1 * a = a

Z haskellowej perspektywy

Obie te struktury są w Haskellu reprezentowane przy pomocy klas typów – Semigroup (półgrupa) oraz Monoid. Zgodnie z poznanymi przez nas definicjami matematycznymi, aby uczynić jakiś typ danych instancją klasy Semigroup, potrzebujemy tylko określić jaka operacja spełnia dla jego elementów warunek łączności. Działanie to jest definiowane przez specjalny operator <>:

W klasie typów Monoid dochodzi jeszcze konieczność zdefiniowania metody mempty, która nie przyjmuje żadnych argumentów i po prostu zwraca element neutralny dla naszego zbioru. Obie te klasy posiadają też kilka innych metod, jednak ich domyślna implementacja jest na ogół wystarczająca:

• mappend – jest to synonim dla <> i planowane jest jego usunięcie w kolejnym wydaniu GHC
• mconcat – składa listę monoidów, używając działania <> jako funkcji operującej na jej elementach oraz elementu neutralnego mempty jako początkowej wartości akumulatora.
• sconcat – składa listę półgrup, w podobny sposób jak mconcat. Jako argument nie przyjmuje jednak zwykłej listy, ale typ NonEmpty (określający niepustą listę), ponieważ półgrupy nie posiadają elementu neutralnego, który mógłby być początkową wartością akumulatora.

Przykłady

Przejdźmy wreszcie do kodu i zobaczmy jak w praktyce wyglądają monoidy. Za pierwszy przykład instancji klasy Monoid niechaj posłuży nam lista. Jej działanie (<>) to konkatenacja (++), natomiast elementem neutralnym jest lista pusta ([]).

Możemy też na własne oczy przekonać się, że domyślna implementacja mconcat, którą opisałem jako składanie listy (w tym przypadku mamy listę stringów, czyli listę zawierającą listy Charów) rzeczywiście wykorzystuje funkcję foldr oraz element neutralny jako początkową wartość akumulatora:

Ok, a co z liczbami naturalnymi? W akapicie o matematycznej teorii mówiliśmy przecież, że zbiór liczb całkowitych wraz z operacją dodawania jest monoidem. Czy możemy więc, podobnie jak z listami, zrobić coś takiego?

Odpowiedź brzmi: nie. Typ liczb całkowitych nie może być w Haskellu monoidem, ponieważ nie jest jednoznaczne jakiej operacji należałoby użyć w implementacji funkcji <> – dodawania czy może mnożenia? Podobnie ma się sprawa z typem logicznym (Bool), dla którego również istnieje więcej niż jeden monoid (jako działanie na zbiorze możemy wybrać przecież zarówno iloczyn jak i sumę logiczną).

Problem ten został rozwiązany przez wprowadzenie pomocniczych typów, które dodają nam ten brakujący kontekst:

• Sum – wrapper dla klasy liczb (Num) z operacją dodawania
• Product – wrapper dla liczb z operacją mnożenia
• Any – wrapper dla typu logicznego Bool z operacją alternatywy
• All – wrapper dla typu logicznego z operacją koniunkcji

Każdy z tych typów pozwala na wyciągnięcie opakowanych weń danych przy pomocy funkcji – odpowiednio getSum, getProduct, getAny oraz getAll. Zobaczmy to w praktyce:

Dual i Endo

W module Data.Monoid znajdziemy też m.in. wrappery Dual oraz Endo. Pierwszy z nich działa w ten sposób, że zamienia kolejność argumentów w operacji <>. Warto bowiem pamiętać o tym, że monoidy wcale nie muszą być przemienne (jak np. operacja dodawania: a + b = b + a), a zatem a <> b nie zawsze jest tożsame z b <> a. Wykorzystanie tego wrappera obrazuje poniższy przykład:

Typ Endo jest zaś zdefiniowany jako „monoid endomorfizmów z kompozycją”. Endomorfizmy, to funkcje typu a -> a, zaś kompozycja, to inaczej złożenie, oznaczane w Haskellu operatorem (.). Kompozycja endomorfizmów to np.:

Przy pomocy wrappera Endo możemy zapisać to w nieco inny sposób:

Oczywiście oba te typy możemy wzajemnie ze sobą łączyć, uzyskując chociażby coś takiego:

Po co nam monoidy?

Kiedy wiemy już czym są monoidy, czas poznać ich realne zastosowanie. Do czego tak naprawdę mogą nam się przydać? Zacznijmy od pewnego ciekawego przykładu z funkcjami w roli głównych bohaterów. Tak, funkcjami, bowiem one też mogą być monoidami. Instancjami klasy Monoid są tylko te funkcje, które zwracają coś, co też jest monoidem:

Żeby korzystać z dobrodziejstw funkcji monoidalnych, nie możemy więc posługiwać się funkcjami zwracającymi np. Int albo Bool. Ich wynik musimy obudować wcześniej już wspomnianymi wrapperami (Product, Any itd.). Spójrz na poniższy kod:

Zwykłe funkcje (isDigit, isLower) składamy razem z monoidami (Any, All), uzyskując w ten sposób funkcje monoidalne. Dzięki temu, możemy zastosować na nich operację <>, w wyniku której otrzymamy jedną funkcję. Na sam koniec aplikujemy ją do sprawdzanego znaku ('a') i wyłuskujemy wartość logiczną Bool, używając getterów (getAny, getAll).

Gdybyśmy mieli więcej takich funkcji do przerobienia w pojedynczą funkcję monoidalną, moglibyśmy wykorzystać funkcję mconcat oraz pokusić się o zmapowanie złożenia Any . (zamiast funkcji map możemy użyć tutaj omówionego w artykule o funktorach operatora <$>):

Przykład ten bazuje na kodzie zaprezentowanym w poniższym video, w którym autor przedstawia użycie monoidów do rozwiązania realnego problemu. Polecam obejrzeć. 🙂

Sam kod można zaś uczynić jeszcze bardziej eleganckim, wykorzystując funkcję fold lub foldMap (z modułu Data.Foldable). Obie te funkcje operują właśnie na monoidach, dzięki czemu możemy uzyskać naprawdę ładny kod, ale po szczegóły odsyłam już do rzeczonego video.

Reasumując, monoid to prosty i dość popularny wzorzec. Biblioteka standardowa Haskella zawiera sporo przydatnych funkcji, które jako swoje argumenty przyjmują monoidy (w tym funkcje monoidalne). Warto poznać je, by w przyszłości o nich pamiętać i móc uczynić swój kod zgrabniejszym, czytelniejszym i po prostu lepszym.

Źródła i linki

1. Wikipedia: grupoid.
2. Dokumentacja modułu Data.Monoid.
3. HaskellWiki: Monoid.
4. WikiBooks: rozdział nt. monoidów.
5. Monoids in Haskell, Martin’s Atelier.
6. Monoids Tour, School of Haskell.
7. Endomorphic Composite as a monoid, M. Seemann.
8. Zbiór ciekawych materiałów dot. monoidów, które wzięły swój początek od pewnej blogowej notki.
9. Monoids on Steroids, B. Milewski.