Posty

Co to jest monoid?

Są koncepty, które intuicyjnie rozumiemy, ale niekoniecznie znamy ich nazwę lub formalny opis. Czymś takim były dla mnie monoidy przez wiele lat.

Definicja

Trójkę (S, f, ε), gdzie S to zbiór, f: S² -> S, zaś ε należy do S nazywamy monoidem wtedy i tylko wtedy, gdy zachodzą oba poniższe prawa:

1. dla każdego a, b, c ∈ S: f(f(a, b), c) = f(a, f(b, c));
2. dla każdego a ∈ S: f(ε, a) = f(a, ε) = a.

Operację spełniającą (1) nazywamy łączną. ε nazywamy elementem neutralnym.

Niektóre definicje wprost specyfikują, że S jest niepustym zbiorem. Zauważmy jednak, że to wynika z wymagania, że ε należy do S.

Przykłady

• Liczby (np. całkowite lub rzeczywiste) z klasycznym mnożeniem i jedynką jako elementem neutralnym.
• Zbiór {true, false} z operacją AND oraz z true jako elementem neutralnym.
• Listy z operacją złączenia list i pustą listą jako elementem neutralnym.
• Stringi z operacją konkatenacji i pustym napisem jako elementem neutralnym.

Kontrprzykłady

• Liczby całkowite z dzieleniem i ε = 1.
  • Nawet pomijając problem dzielenia przez zero, to pojawia się problem wyjścia poza S. Np. f(9, 2) = 4.5, ale 4.5 nie należy do S. Zatem f nie jest postaci f: S² -> S, więc to nie jest monoid.
  • Dodatkowo, dzielenie nie jest łączne: (4 / 2) / 2 = 1, zaś 4 / (2 / 2) = 4.
• Liczby zmiennoprzecinkowe (IEEE 754) z mnożeniem i 0.0 jako elementem neutralnym.
  • Mnożenie (ani dodawanie) liczb zmiennoprzecinkowych nie jest łączne. To właśnie między innymi dlatego liczby zmiennoprzecinkowe są nieintuicyjne.

Monoidy a programowanie

Dzięki temu, że f ma sygnaturę S² -> S, to nie można „wyjść poza zakres”.

Mając monoid i wyrażenie typu f(f(f(f(f(a, b), c), d), e), f) od razu wiemy, że jest to dobrze zdefiniowane wyrażenie (tj. zwracane i oczekiwane typy danych pasują do siebie). Nie musimy się martwić, że „gdzieś w środku” pojawi się wartość nieoczekiwanego typu. Cały czas obracamy się w „świecie esów”.

Co więcej, możemy użyć innej notacji: a * b * c * d * e * f, ponieważ łączność sprawia, że nawiasy są zbędne. Wprost z definicji wiemy, że (a * b) * c oraz a * (b * c) znaczą to samo. Wnioskiem z tego jest to, że napotykając wyrażenie a * ((b * c * (d * e)) * f) możemy je od razu uprościć do a * b * c * d * e * f.

W końcu, istnienie elementu neutralnego przekłada się na rozsądne domyślne wartości. Jeśli chcemy skonkatenować wszystkie stringi w liście, jakie powinno być zachowanie, gdy lista jest pusta? Pusty napis jest właśnie dobrym kandydatem na domyślną wartość dla takiej funkcji.

Jeśli mamy pythonowe wyrażenie functools.reduce(func, iterable, initial), gdzie func jest naszym monoidowym f, zaś iterable zawiera elementy z monoidowego S, to ε jest często tym, co chcemy wstawić w miejsce initial.