Najprostsze typy danych – Monoid

Dzisiaj na tapecie ląduje jeden z najprostszych i najbardziej ogólnych typów – Monoid^W. Definicja z Wikipedii jest fajna, ale zbyt abstrakcyjna. Prostsza i w pewnym sensie lepsza, bo pracująca na kodzie, definicja może wyglądać tak:

Listing 1. Definicja Monoidu za pomocą kodu

public interface Monoid<T extends Monoid> {

	T zero();

	T apply(T r);

}

Metoda apply to jakieś działanie z dwóch obiektów tworzące jeden. Musi ono spełniać warunek łączności czyli:

Listing 2. Test łączności

@Test
public void shouldApplyBeAssociative() throws Exception {
	T m1 = getSome();
	T m2 = getSome();
	T m3 = getSome();

	Assertions.assertThat(m1.apply(m2).apply(m3)).isEqualTo(m1.apply(m2.apply(m3)));
}

Inaczej mówiąc mamy do czynienia z operacją, która spełnia prawo a + (b + c) = (a + b) + c. Prawo to jest tak naprawdę wynikiem tego, że monoid to specyficzna półgrupa^W (ang. semigroup), ale półgrupy do mało czego się nadają w praktyce, bo są zbyt ogólne (albo ja nie potrafię ich użyć w takiej ogólnej formie).

BTW, tu widać jak niesłusznie narzekamy na szkołę. Warunek łączności dodawania jest omawiane w drugiej klasie podstawówki? Jakoś tak. Szybko trafia do zasobów „wiedzy zbędnej”, a znając je można już zacząć programować i to całkiem ogarnięte rzeczy.

Druga metoda zero reprezentuje element zerowy, czyli taki który dla operacji reprezentowanej przez apply jest neutralny:

Listing 3. Działanie elementu zerowego

@Test
public void shouldZeroNotChangeResult() throws Exception {
	T m1 = getSome();

	Assertions.assertThat(m1.apply(m1.zero())).isEqualTo(m1);
	Assertions.assertThat(m1.zero().apply(m1)).isEqualTo(m1);
}

Dla dodawania będzie to 0, dla mnożenia 1, dla String pusty ciąg o zerowej długości.

Motywacja

Ale po co nam to? Przy okazji rozmów z kilkoma osobami o nauce kolejnego języka przyszło mi do głowy kilka prostych ćwiczeń, które pozwalają na lepsze poznanie możliwości języka. Jednym z nich jest implementacja prymitywnej listy za pomocą monoidu właśnie. Innym własna implementacja String. Nie ma to na celu zdobycia jakiejś super wiedzy czy też stworzenia czegoś odkrywczego, bo listy są powszechnie dostępne, ale zaznajomienie się ze składnią i jej możliwościami. Ot ćwiczenie, które każdy programista powinien znać i lubić (bo pozwala się rozwijać).