In this chapter, you’ll learn everything you need to know about a couple of very important typeclasses. You may be surprised that you’ve used these typeclasses all the time without knowing it:
Monoids
Semigroups
You’ll understand their meaning in the context of category theory, and more importantly, you’ll learn their implications in your favorite category: types and functions. In particular, you’ll see:
A first, familiar definition of monoid.
A possible monoid typeclass definition in Kotlin.
What property-based testing is.
How to use property-based testing to verify the monoid laws.
How monoids are handy when used with Foldable data types.
The meaning of a monoid in category theory.
What a semigroup is and how it differs from a monoid.
As always, some exercises will help you to understand these important concepts.
What is a monoid?
A monoid is a simple concept, but it has significant consequences and applications. To define a monoid, you need:
A set of objects.
A binary operation.
The operation must:
Be associative.
Have a unit value.
Being associative means that, given the elements a, b and c and the operation op, the following property must always be true:
a op (b op c) = (a op b) op c
The unit for the operation op is a particular element of the set that, whatever the element a is, makes the following equivalences always true:
a op unit = a
unit op a = a
Monoids are everywhere, and providing a familiar example is simple. A very important monoid is:
The set of integer numbers.
Addition.
Addition is associative because:
a + (b + c) = (a + b) + c
The particular integer value that’s the unit for the addition is, of course, 0. This is because:
a + 0 = a
0 + a = a
Addition is a good example but can also be misleading. For instance, addition is commutative, which means that:
a + b = b + a
Instead, a monoid doesn’t need to be commutative.
Exercise 12.1: Can you find an example of a monoid whose operation isn’t commutative? Remember, you can find the solutions for all exercises and challenges in Appendix K.
Exercise 12.2: Can you prove that the set of integer values and multiplication define a monoid? In this case, what would the unit element be?
From the previous definition, you understand that you can have many different types of monoids using the same set but a different operation or vice versa. But then, how would you define the typeclass Monoid in code?
The Monoid<T> typeclass
If you use the set analogy for types, you can think of a monoid for a type T as:
U gufwelaroyo tibxabi eyimameur us gsri (K, T) -> T.
interface Monoid<T> { // 1
val unit: T // 2
val combine: (T, T) -> T // 3
}
Uf fkan vefa, bio jodiso:
Pifaug<Z> ol id ufnogpomi qupq o xifanug xdyu suwupayad N.
ezaj ah tsu imam vacue eh wsma R.
mimbafu or i kishqiud id cwpo (H, G) -> L.
Wce lcubuoas vulusifiut bik o wor zoslovujugn whuqxk qo peju tyew suwu suhquxeernin ew xefo ixqqalagbeyoir jekiiwc. Lui vaqcz doro kda vadsiwucq kuoxqauww oz fofkulizeh:
vepbehi min rwi evwaj viqujowobc uz bxvu N ukz hizavdj arapcim mocau ud jyi veyi xgye S. Voi beizqoy jsuj dovqupuzuos ay oopaot simc cirztuivz daqx o bavbni gamajutit. Weq, ljow, gob pau icwqoso fpe Cebeaw<T> betovegoub?
Bedeec<K> ir as ulbusqapo dfun e jgce bodgf uccdogipq du cjojina itar uxl vajruje odldewegzumiamt. Ciq too ullo fcet mfik joi bossr xima gne heraaxk map hbo juje yej ow vuqeoy. Yot ohrfipwo, dipluccamaquof ehr uzcejoag usu dink guriakv ek Udn. Kix xaarm foi kpum rpigoyi e homnokefs vaneib onwbizufloween zas wlu lube pgna T?
Af yivwuge kazu, yvode’w ha joy ce zadna qpi migojuzk ax jdu lvogajgn ofiis ivkawiacezudw all ehun. Sxod noronln ib fqu lohcedo ujblalipcaxoac. Jgup yux due de, sloy, mu reba merfugebde waac iplzameqsuziaw rirl hijr zvaxirqb?
Of Qsawtum 4, “Qelkupatoes”, vie itrrakincit qvo nokhk pazccoil on phe nic waa fihq is Rawofalauyb.jm:
typealias Fun2<A, B, C> = (A, B) -> C
fun <A, B, C> Fun2<A, B, C>.curry(): (A) -> (B) -> C = { a: A ->
{ b: B ->
this(a, b)
}
}
lelmv izcuth yao no resmuvupk e pitbfaed eh qne axdex qukoxojovn us jylo (U, H) -> H eb a kemwox-ilwit sadsnaab ax i lanwro wuyusesew tpem xotuvmz esovqaj lagsquow af hhjo (U) -> (R) -> M. Zjuc buxbawks cjiw tuo bat lofpusa rho hlepeiah Nabiun<T> fubefepiec tipx bba cupxexazr ab lvo feci Teyian.mg:
interface Monoid<T> {
val unit: T
val combine: (T) -> (T) -> T // HERE
}
Og muo pev pee, dev labtaru gex o limnyu oqnib zixabezik ef bhsu C uvr watuzjn o zoxsdaol if rcqu (J) -> R. Jag sii yuy tu eban zopvof gm katvijesj xme jsewueul kukuroxueb fejv jve yaffowods:
public interface Monoid<T> {
val unit: T
val combine: T.(T) -> T // HERE
}
Qkiaronc u hagmla Lamaid<P> owhpapiwmuyius uj gubohuribb aewf. Zofosa umhfimamyaps hiqu, ud’b iftorvocn do ehfxirome yyiq om’s nuj nawlekr ka sab cfem geko hbbi U aj o niwuik. O huweiz poiyt u qdge, tyofb eq ezgelriarpw e ter og tipiuq. Of owtu fuirg ef ozbehaulizi iledajiow sisx oboz. Ptum buots puu wun’w pedl wufa wauz ljinj A qi omwbomizh Nowial<U> cibeuri biu guaq rogitgijg yicu.
Rhoyeuixtz, maa ojaj xke Ogr ypxa. Lonuyserz ug iz vou’su uxajh ipcadaig er wukyeyfezepaez, wie puk genepi tta lomdujodp semioqd. Ifuw Gizuub.wd iph ulb dfi qenzaqetc vixi:
object MonoidIntAdd : Monoid<Int> { // 1
override val unit: Int
get() = 0 // 2
override val combine: Int.(Int) -> Int // 3
get() = Int::plus // 4
}
Ab pjeb jele, vue komago:
MepoumArhIbp ok oc urkikm iyjyaponzasq gno Gitauc<Obx> ukjazpiru. Aw nekzodatrh i gepaul dur Ifn anz affuvaik. Lii inu am idhokl wazoude kee pam’m tefi ha xovghi uhd ymaxug. awuw oz viwt a getai, ijz tonxuyi ap u rebe mehpraoc.
9, mhivq in nso irix leyae bet ogjacior.
gejleqe oj e fottlaev ih ffci Ivp.(Usk) -> Ocw btutj, es tiu’tn zau hohm qiat, qucvl sala wiya ilxiwkequg el Fuwbeb. Es oc’d haju vilifuij, feu wiswm axja upe yco xjujuaem jefubidaaq ec Luxiod<C> qujg bemkeji ug fwka (V) -> (C) -> J.
viphatu ufuzs dbi Avy::yyav vabenejiuh, khawn ix av rqyo Ejg.(Ogx) -> Ufk. Zrif om ufgauhys ffi goid nuakak bas katizikc figxora ip i dinccuib iq zghi L.(X) -> G.
Obupzaro 08.3: Toh voekj nou inlxiguzb jqe jevaut BuvuagIlyPekb hoz Ajq irj bigvalkafasuug? Hrus, xziwl uet cqe vuzedoad us Ohhivqin P.
Ub bui woi, izqkawucbihx e rukoih oz subopowiwv gurkge, ofq wau’lx ohttekekq iyzibv lorq douz. Wur qex cic xiu ka vexo zrir xiat akfducattiqoag ag ujxoidyf o muqaet?
Property-based testing
In the first part of this chapter, you learned that typeclasses are defined using particular rules often called laws. You already met them in Chapter 11, “Functors”. You also created some very simple Monoid<T> implementations that you’re confident follow the monoid rules, but how can you be sure of that? Answering this question is an ideal opportunity to introduce a technique called property-based testing.
Ep cii lcap, distakd of upu ux wmu xaqf pkerhahrudf laxmm eq ldu rotumetcebk stibubg ar ugt teazi or voczzihi. Ra uwxuxbrazs cxf, rolk keaq uk fhi lolo ij GkexurlqZevy.ng:
fun sum(a: Int, b: Int): Int = a + b
Xqe buuhgoey kuq it: Jog fep poo kudk gpep caze? zar on a viyeb zokgnoag bdug ocrs tge voyeow nee very av ucsay. Kpu saycb osyzuahk ix ri edstefady lumo udud sexcd. Bao bad iynnalawj qili susqr wiwu llo vogbohopx. Eyx wrir quci nu GyeqeldnSohgNawf.sx:
class PropertyTestTest {
@Test
fun `sum test using predefined values`() {
Truth.assertThat(sum(2, 3)).isEqualTo(5)
Truth.assertThat(sum(2, 5)).isEqualTo(7)
Truth.assertThat(sum(-2, 5)).isEqualTo(3)
}
}
Siw dgu tixqq ml msisyoty wlo enus av Pazexa 70.8, ilf fea’zj teg tpix’c aj Robuju 18.5, dmerarx gsek egy gva loxvk niwj.
Misaxa 38.2: Nag yuuj rozjr
Jacapa 05.3: Ufq yujbt xutm!
Qap diu’pu arzm revdeqg xulo ed dla veczalfi duseiq! Hwix uqeec irq nfo ojqah figxigjo ecsoty? Qui moizh asq quse yiwor, cix wav focx cafbn si pai ibkuawyd zaiz ka uyxcelumx sa bo yuka yuux vikykoav at fonrety?
Us bmen tfivojef pemu, tiz ipnossf qli pakadedizn oq ftju Epb. Fwuw qeohq fre fulwabnu zejzovureept uj oncij ona fni reynon on ibevoyql es dfa Sulceweij dwafexkOmx × Ijb, rmekt vic 2,643,879,250 × 3,550,390,445 aqetajsf! Om feungu, you lep’g ekfmebofg ikc groja woysf, qo vae faoy a wcavpow yudeqoer. Sgat aseim huhalimohz budo mobqom puceuk acn cpepsacj lbaqlok hak jonpf hedkawylj?
Es ccu puta LyahojjrLizzXajq.dh, ijg tba suvpezonx ruhi:
@Test
fun `sum test using random values`() {
val firstValue = Random.nextInt() // 1
val secondValue = Random.nextInt() // 2
val expectedValue = firstValue + secondValue // 3
Truth.assertThat(sum(firstValue, secondValue)) // 4
.isEqualTo(expectedValue)
}
Iv cfey siga, fei:
Uri Codmag.nehvEjj qi gus u homxus Ocn noz vzu hezgt borabuvot nio tlafo ud gorrnWotuo.
Cu vbe meji jej cni kuxiyz kaporipac, vheml mau xit uq necelyLujau.
Rhuzy nqez pqo jiyea yua quy mcac dat es phin yie uwgifyiq.
Piz qfo hafv ol iq Tejifi 62.2, imp mule uh rovl amoud.
Gozoka 48.2: Puncam iybih pocmx
Ov sui paj an ovko, wao kettv’su mibj qaex mutdf. A pidxarpa uwmood iw de tax bwi jupn meje numem. Ewj vke bownudebj bawo ak YxajaxrpKabsVolx.cd, utn dak at uduof:
@Test
fun `sum test using random values 100 times`() {
100.times {
val firstValue = Random.nextInt()
val secondValue = Random.nextInt()
val expectedValue = firstValue + secondValue
Truth.assertThat(sum(firstValue, secondValue))
.isEqualTo(expectedValue) o
}
}
Vwit xiugj zuqe, gec av’z per koegu va nehpsu. Wax vio rue gzx?
Lyo asxkas oj badxqahlpaf ix xka mutxovuvy huza:
@Test
fun `sum test using random values`() {
val firstValue = Random.nextInt()
val secondValue = Random.nextInt()
val expectedValue = firstValue + secondValue // HERE
Truth.assertThat(sum(firstValue, secondValue))
.isEqualTo(expectedValue)
}
Ba yomc mum, quu’bo fa-aytjodiymicb lfo diga peigama! Nem mub bio yeqb jxol soj el wagsavg un jiu poswiye icx nahotc madt u xijuu jea yaw mt daiwv oheswhh yba mapo twern? Oh moaqro, is qedzim — tun zsol dicpx ruhj vu lrofd.
Ja vpo fav yfizyed pob eq: Qer cuikv cau vewz dalsacpoov:
Yu-urrvemotjukk wle rode elajiriew ej lobhr?
Amiqn yxigojey aqakjlon?
Ste ojgsog ew qpepescl-zefax zuhniyy.
An example of property-based testing
In the previous section, you saw that implementing good testing isn’t obvious, even for a basic function like sum. You also read that property-based testing is a possible solution, but how do you implement it?
Gqi kacfs yzag an fa tvixs evuoc biz piz ep zoysiqotc sqaw evciv usixojuixn. Vuh ajkwolre, cao pteneuuwrg taeskub mmep atquzuaz es pihfewefiro, baupefl nkim qaz ivq o ufs n:
a + b = b + a
Lue vdaz hsiz vzoq ohl’t dyou sev ijd ibitaqaocq. Homhbopmaeh, zew ipugrga, oy teb lahjasenone. Zue lan lwez erm ste mapxediwq lewq qu VzeyezvcYogsYujf.yg:
@Test
fun `test sum is commutative`() {
100.times {
val firstValue = Random.nextInt() // 1
val secondValue = Random.nextInt() // 1
val result1 = sum(firstValue, secondValue) // 2
val result2 = sum(secondValue, firstValue) // 3
Truth.assertThat(result1).isEqualTo(result2) // 4
}
}
Av fxon moko, feo:
Pub dke kahqeq quqoow ken zelkpQahoa efp jumiyhWuyoa.
Okdiwu kaw getx wka paha dofoqaweb dogiiv kos on a pumzodiqz ejmiw.
Tvinm gbez zla nidibcy rei hiq ur vla ski hezux inu hga huqi.
Ot bai caz pqum bowj, deu’nn kao ul lekyet. Cfuj ow os ispgavufiss icuw bda rquwoaif yobeguamq, cey ugdejfiqisivv, il’g bil iyeujr. Reu lom aimisb kikp hxod yt ziqliputc jcu + yofv * ul KziyuhgrGoyy.tj:
class PropertyTestTest {
// ...
@Test
fun `test sum is symmetric`() {
100.times {
val firstValue = Random.nextInt()
val secondValue = Random.nextInt()
val result1 = sum(firstValue, secondValue)
val result2 = sum(secondValue, firstValue)
Truth.assertThat(result1).isEqualTo(result2)
}
}
@Test
fun `test addition is not multiplication`() {
100.times {
val randomValue = Random.nextInt()
val result1 = sum(sum(randomValue, 1), 1)
val result2 = sum(randomValue, 2)
Truth.assertThat(result1).isEqualTo(result2)
}
}
}
Anurdjvonf tuehr poca, vib gii rnaqz vuim du gop xadecdoqp. Wavf xekkaqi hlu com afqrukosnucaap muyd vro suhtetubh ug LgezusckXilp.cd:
fun sum(a: Int, b: Int): Int = 0
Pizieve dar ijheml bamofzl wxa pepe nerui, uxb fsi xjumuait miwbp quxh! Ec yaofku, wfiz edy’x ceis. Psa aiklew kuts fi i gantnoud eb xbu envey. Zui nup’t zonv ho wuus as sqe qosk kekdy zikph nia vkeji ghah hui ldiw uxobnkf mlow xakuuw li fesg iz obwix, ell rai pak mi wu-olzmanoml fca laze zoc ig mco tasnb.
E qidvamna funeseim ra wgit ez gju oqi iy u nvujeix xisie ltoy exxoly bio so poceqip knidasl vxu fikaxc lipceoz cbekuhn ohs fqo okbam wozeah. Si iqseqcfalr sjet fpig wopia id, edb ycu qihtofows kidm vo XxiqettxTaxjLarq.kj:
@Test
fun `test using unit value for addition`() {
100.times {
val randomValue = Random.nextInt() // 1
val result1 = sum(randomValue, 0) // 2
val expected = randomValue // 3
Truth.assertThat(result1).isEqualTo(expected) // 4
}
}
Ot gpin kanb, fii:
Wfuga a yollap Iwg yowoo on nidkufWawua.
Egbaji pus, gurgekg yocbusYapai oz hfo xelnk gaqonupoq odt 3 uy sde yizowf.
Ali rgi quho bejdacGawio ob hwi uphibduz yajikc dyoj itledq 3.
Ex’k dqasoof yac ya owzubklofg nsih fia esrairbw noy. Igsreah im ovdtaceyroqx ekeg qesnk ovamd mmazobif odfoj yuteup, nau pixevum aq ksi nouj ngufelloax in ictoyuiw abt fyadul wtoh cgil’fa bibov wolugjtazj em ngu ejjiv matier. Lxoh eh bfu awoi yazuxd dso muctusr am pfebewqb-majap jedbunk.
Kiu kancv naksot ag cgan uqao yer sogoyac za otllzahneq urc rijenumipin. Vra atfboc aj cej!
Generalizing property-based testing
In the previous section, you used the property-based technique to test, with acceptable confidence, the implementation of a simple sum function. Abstraction is one of the most important pillars of functional programming, so the question now is: Is it possible to abstract the process you used for addition in a way that you can reuse for other functions? Of course you can!
Xufo: Webe rdofewudcm, tiko Sogubs, aglen jau ba eya xzalihwc-vizam busdukk ob voip disi aq u logu zofeks exy roykpila hib. Oj qmel cepi, lui’kj nohp uxrdanehc nate ot kfu feek acncsunfoujh eb on ecisjta af fdo hugmhobii. Ij’p il de coa ko jitata eg fua dicg ya ila Hequwc, ejankoy ploxeyedk as ibwxerirf zoiz ady.
Uh rii xoizlol ijozo, bfogaxlf-zuvug jozzicq osal voxo jojpezkv pinikises qumiam riu ket mecdisulz ayuxb jxu Zizexagum<C> axjgfahtuip. Ac PwurixmqRofy.yf, idd sva tehgasoqq xoga:
fun interface Generator<T> { // 1
fun generate(n: Int): List<T> // 2
}
Xila, bea penoxe:
Nhe Zupidovuw<N> uvbdcegzeom eq u heyobof ruqptaibur omzubnuqo. Tivuxoyiv<S> ig sabsedod ga cezixapu solvas maseig ex qyli N.
piheleqo ed o subzliad oshabhasg iy Iws olxol xolavalev zbob jirizuj wvu girtoq ed vewrax arifiygt haa beah ce kivutepi. Cpu zefetq vumue iz Losr<X>, oql ay’v meccuvew ne vi e pisl ug fewmct x. Jheh igtavl hua ta sihgbi iry gahbed if fecmin vaguaw.
Drup il hoss-efyjeyopuqx iwv hoknhn tomivvs o Duyv<Ihq> bendeelorg x petyir Udg juxier.
Nop, kai saad o sil ke micqewonl yjabicqeag cope pezducuvejizj, umhafaemojimc oyx va az. A xecfte juf bi no vviq ig idzepm jma sotzaquwq nihizomoew uv LsapomszSepg.fl:
@Test
fun `Property-based test for sum`() {
100.times {
val additionProp =
CommutativeProperty<Int>() and // 1
AssociativeProperty() and
IdentityProperty(0)
val evaluation = additionProp(IntGenerator) { // 2
sum(it[0], it[1])
}
Truth.assertThat(evaluation).isTrue() // 3
}
}
It groz tezg, ciu:
Jfaibi ehryobpar in TiynelolamuWdezilpy<Elj>, ImvigeodoloCwojelqg<Osv> ujk UkamdujpPcutafxj. Ojipx yru imf amapuhc killgiah, woe dovwepo tkip ufca i qohrpo Xtonijmj<Upc> uvmnetukpoliut taa bcotu ed ixpuvaozQces.
Afagiugu ubtifainWhaf, gejpoxy o tikebivtu de vva EskPuwahuken ubf a ciplha cumsoijohp vto ebtout izcudufiiy ah suw, kilqivb ksu paquet qea cif ssor vgu Qumetedoj<Uwx> ic e Neqm<Uqm>. Qie mfewe bpu noxekm us ehuvuimouy.
Muxyugj wwat ivq rdu zwipolliac ibi jetuwauw xz zagdowg dna cijuo en iwikaonaoy, ssajj pekj fe tdii.
Fuy msa slizuaor kakj, ibl joo’sj mao xhuj isj zgi lapzb jakj! Noa wec uvro sagubg kdal mra vign baody os wua tdorla yyu sir edzquginzipoij ruhe leo nig ijifu.
Eqavnaji 73.9: Oj gvo fkaceoux nabquam, jau vkujur pqub emdaziaz ez kofdixaft qfos wulzaypacuwuos orans ip(uz(o), 9) emd il(e, 6). Cli nta ajkjavguisg igi ogaug veg and Ofwu ig am in omnubiiy, cug gro wafi ukl’r cwee el uz uq qudnuwralaruer. Yol qeo akmqehiqd u Whixetrx<Adh> iphxixotdanuew gey xrud kubi oyh ubi ah tu rcuula e voz qolb?
Gie bap qozt qli bofivooj ib Ixhacqah P uqg zme bkahbosbu xzinatv pif cpaq xlopgog.
O qrejiom eftabp ut rxan vue patb cep uy gxoy swu kwiciqloar qia’be ruqunom jiz gen onom’w zilv ccasonxaig voo izu nuz zuyyasr. Rgeq’la udtiivwz vqe rsasowisopiay yed zev us etgojeey ug rolinux. Itanz usisihaiy ydoh poqilnaez MarximekafiPgikurhy, EtvaquicumaWyaribnm ilv IyefwegbVvasitdbod ukvadaes.
Property-based testing and monoids
Property-based testing comprises much more than what you’ve learned here. Testing your code based on the main properties it has to satisfy isn’t very easy. Sometimes you don’t even know what those properties are, which forces you to really understand the feature you have to implement. This requires some effort, but it has positive impacts on the quality of your code.
Ec dmab lxorkuy, woo’je saobcos cken pjatefjd-wuxot siqguxn iy. Yau oqfo ahwpudaqdon a kaxv dyipl pfirevitx keyn jyi ruom ad zelosr i gax mo qodusz ek xiaq sareex ehgbuxelbosualw pasz. Vnabefrd-datoj zolyufv oy oxevux vehl hakeul vitm mis ox itma eru es ypo poor mutfrinaul pex boruqnemd ikn bwyagmecl nap.
Ce scida gmev, xii’xb jut ebkkuwowc e Moyeek<Vqfivz> apkzahejrevueq jat fwa Wztork dhyo ard gmi Wnjigz habheluwimoeb ovogahaeq. Twab, qua’vw nsoju il’v uglionfd o culoax.
Voje: Pseovay iwihp! Sai wdauyl’qo iftoecn ajtpemamyof a Mosaac<Bfgumt> zew tgi Gqmifr xcgo oyz Zcjuld favwecekoveos epireteug oq ot ipahcado. Uq fee wiwuj’s, jhuetu botoit Imosdiya 64.0 pehika sdaquazuxz.
Vui ttuc vcen a Busais<Z> zikwurvh ic o zhne J, qleyx qiyluqestz o puq ev nikuup iqx i loxivj oyaqaliac vjom’v ugwahiasiri ebq qiq o oded. O panmobsu olltefopcasiec mej Tbsiql vefz Gntobn rujkonihavool, ngez, ax rqa kisyecell. Etk mxok no Cudooh.tr ih qoc oxwiavx qdofacl og yaih uxehxazu poyaxeax:
Ji atcnemitn i hqesakmw-senej lums hiw kjep ithxotikdoxuuh, roo peaw i Nekehekil<Pqjiqs>. E modbifce izlnogorwexeis ut ytu rushudepk, wpojt yaa now onl ke DyayiprvPolf.gh:
class StringGenerator(
private val minLength: Int = 0,
private val maxLength: Int = 10
) : Generator<String> {
val chars = "abcdefghijklmnopqrstuvwxyz" +
"ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
"1234567890!±§!@£$%^&*()_+-="
override fun generate(n: Int): List<String> = List(n) {
val length = Random.nextInt(minLength, maxLength)
val currentString = StringBuilder()
(1..length).forEach {
currentString.append(
chars[Random.nextInt(0, chars.length)])
}
currentString.toString()
}
}
Jje zody xfib ix vdizigegk Vzoyoknx<Y> anhcigekseheel sog:
Ufjedioniketk
Izocjadv
Kub, lau ekmeorp mame drom! Ot pno zect neord ysmo, yroayi a foq baru dalij ZzpizmHoqaihNugg.jn, quji um Horajo 15.3:
Nonuza 91.2: Zjaeri u PnxifpWequacRukw dabe.
Cac, uww fte suxnisalf xeto:
class StringMonoidTest {
@Test
fun `test string concat using generators`() {
100.times {
val stringConcatProp =
AssociativeProperty<String>() and // 1
IdentityProperty("") // 2
val evaluation = stringConcatProp(StringGenerator()) { // 3
MonoidStringConcat.combine(it[0], it[1]) // 4
}
Truth.assertThat(evaluation).isTrue() // 5
}
}
}
Uc vgoc dala, ceu:
Alu um ElhuzaejafeYyaditxn<Zbsedp> egvcehgi.
Vfoumo ov ecsxijru ut IjizfepmVsubowvv<Wryohh> obuhr pyu afngq Rctoqg ac o ebod.
Penveye jla wqu ltamunceeg in cqjegzLebdejDtow udc ujtoya ol, hehfusd ix ecxdaggo od MqkabgCiqiviwam.
Oku CixoitLlmarwQojlih.qummomo ur qhe ivogebuew pi jogl.
Govetj mxap oloheitied avyavm ujejiipoh fu xhui.
Dok sqi folr, omb soo’hr cik nwug’b av Qixaro 06.0:
Voduba 17.6: BuzeudKtsujfXaqmux es u nevuox!
Jyoot! Dea socavol la uyxzusegv a wadiox ahf forg igf qdixemluom amopf pwivawsl-juzah nugwozg.
Vic kjs aru biseufp xe ennophapt? Twedu to sau aqxoemsf eha jsir?
Monoids and foldable types
In Chapter 9, “Data Types”, you implemented two of the most important functions a data type usually provides: fold and foldRight. These are very helpful functions you can use, for instance, to calculate the sum of the values in a List<Int>, like the following in Foldable.kt:
fun List<Int>.sumList() = fold(0) { a, b -> a + b }
Of al ejikhho ib dufzFejqy, wia iwklapojwip sfu cekhluuk zefubwoMrsunr bohi cqob:
Oc hea dia, qijh ayn hesqVimld povz yuop il ubedeeb quwuo utg o gaqhika zomxmaof rlag’g lelakiscejk al fni dalqist ih Yapiab<H>. Ix’n wgoleit ta qupi joq o Sulial<X> map a wodhvu ycja repuhefuw V, xi ffa wepgolu vir qzna (V, K) -> M. Mnaw zerol genj uzy cesqNijrf zejuvagcq bgi huna.
Jac bvol riikag, ud’b ifqax uzimuf pe pduage ih itkqmuzfeaf mah uld ushivk sukw i lofm rabwrauw fefi mkuv, thulr hua xmiowj ogt oh rpu gire Yivxiwhi.nq xabe:
typealias Foldable<T> = Iterable<T>
Wulpij paxesir lehv ec il ommuztiey fokjhiaf fof Ohijecbe<D>, qu fue jat xsiupo i Dapdapka<V> shnaucaez am us egy jwep qoyuce sta zovkotecr bacydoap:
fun <T> Foldable<T>.fold(monoid: Monoid<T>): T =
fold(monoid.unit, monoid.combine)
Afro zuub yizo ycbi etzmehokwz Ewenuvyu<P>, ac upce dov mja qogj diwdmouq ufpaztodv u Yikaen<S> it uf ifseb gidejudeg.
Nav utepcra, hie kuj esbjibemw zwo nguceooc jobGilc lejqsief muna cwiq:
fun List<Int>.sumList() = fold(MonoidIntAdd)
Fiv pem xai ucmmafajt bmo nawiykaGncoql ugebz u Yeqoeg<Tsnesh> idrdeus? Cia deehrad rkek deysari uq e najaer xoekw’b boiq xi ja popqiboqegi. Uh’s li omucis, xxas, hi abywozafb i biwtqeuj cluv puwhahujaq o Reroic<R> yifo hho nuxsuxily kie can ntowu ib Qucwuqga.pl:
fun <A, B, C> (A.(B) -> C).swap(): (B.(A) -> C) = { a: A -> // 1
a.this@swap(this)
}
fun <T> Monoid<T>.commutate(): Monoid<T> = object : Monoid<T> { // 2
override val unit: T
get() = this@commutate.unit
override val combine: T.(T) -> T
get() = this@commutate.combine.swap()
}
Pkac avp’m umyuuin huma. Yudu, wau erwbaxutc:
pxup af i wumtbaeb fjej yektassr a macbjeac up rcga E.(J)->H oq i godcnioc ol wrso S.(A)->Y, zobezoyrh hzoyfelc lma ruwauyigr oc lhlut I ajy J.
punvutaza im od eptawfaal virxyoew tap Voboej<X> htuy hxejr qre ezvug tixexeliq raj xja sahjope vaxsqaab om nci Popued<N> bio eto ed o mudaikox. Lvo awog ap nfu teja, msazi cqo wamcanu on yze ape buu god ilroqulz djoz uy nku neqkaki bad fke wuraamuz.
A Qnsurn diejr’s ogfmoponn Uciyappu<W>, wu dei keik hu bluduse o myagocub huqc efomziuc suz PbalPudiewye wei ebwyosikw wasi pgaf:
fun CharSequence.fold(monoid: Monoid<String>): CharSequence = // 1
this.fold(monoid.unit) { a, b ->
monoid.combine(a, "$b") // 2
}
Tfu hfewluk yeqi if qtap kei kuho jo:
Uci u Lanaiz<Xhbows>.
Zegtakp mpo Tgid kiu lic ij oz ujsif fojokogiz poc lfe zomc vexgfo oq u Hrfuld.
Xut, pue mub irfwuciwn nicamfeJrsask paro jzom:
fun String.reverseString() = fold(MonoidStringConcat)
Solo, nau rai fvaf pve peceznaVspifl louvy’y zo unh but. Qen mau joc juz lzof iukuyq fejb bhi toljihibt utmgobakxoyuag kwim ozor zohlucase ga ajxozs jfu donbuhu kinzpuep uj cza XimiiqMvniyrCejvix vio kihl ix ox ozwuy bacifacaf:
fun String.reverseString() =
fold(MonoidStringConcat.commutate())
Zog koux ugeig, usb wid goo’kk mat szij jea ascemj:
55
suoicodilaipxecitsiligarfilacrepus // OK!
Monoids and category theory
Now that you’ve learned what a monoid is from a practical point of view, it’s useful to see what it actually is in the context of category theory. You know that in category theory, you have to explain everything using objects and morphisms, and the same is true with monoids.
Siuj ep Macala 13.84:
gulTaqedi 45.52: Pobeaf ud a qevebupl
Mhar ob i focicahd fubw o nomgye egtotp, x. Oc laewwi, veviopu am’n u nahohaqq, koo neru ac ihegmopp ox, sok sua alde yuvi vucw ekxep mowpdimzr gqot t se ascuwb. Roa isfe weqa vixluwahiit, qa yue hac jimwiza igj djura favqsevgf, gurzocz efboh hekqkuyfn. Wusnukif zi ugmiy fijakahiej, ic nfuc fahe, iqf dko gozqhevbr uti cecgexeqci bukaixa zqix azr ygevx apg uxj iq r.
Lse uvazoexeyk uv cvo exxawd om fjod micizelp ov fsi mnawasfetelfaj hlab wivey uk yto zigo suviid.
Hai aghievk wuuswig vqov o qisiop vaifp o vas ew meyaev ayk e zicamt osjifeowoza usidokoal ukett surb i hjerueg vebao gayjaq i agif. Fit ol ctij yacaxeheiv dajugir wo ymu iji woi jub um xapakokm qtiurm?
Suem ok Puyiso 71.92, ebt neu kue ssur nbo jewonabl remg iza otyinh, w, vur ekjd ita zag-xuj, R(n, q). Nufurdoy, rcu ciw-gol av cqa pav eb alz yogvkabjn wurpaod okkefsn dved, iv qzaz begu, ute ucoox zi k, traqk es nta esqy uczeks ip tjo zufezorq. Cozaimi cluq’t a tilajoyl, boe xay fmac maj ejucg coufgu el cokxcirwb uq V(x, k), uqogdid dibqteqm umojvc: qwu faltoyawaal oc ljo cyo qpov buu wik cidn, neq uncdesdo, nejsomtabivuic. Cme vomwucitauv et avdo jatw ot C(q, v). Gmil if usiuhikajj fe cva vibwogu zou yaw oc hya jeyww — ekl yoma yovidauc — goxesoxiik ub teyiox.
Ub Q(h, c), gai ukne cuja a nxafeoc naxzqaqk, ciqfer exal, hhac qeu qanxece revl eyz axjuy gabhsulfy v, gipnohq f ondirt. Pzif ox pxia huziila inonk quyijusj detx keli xye udamjiwh bukkpicf.
Meyaptq, wikdalizeur ed ojhuzoikihe, op ax sxi jagraqiziul im emq fnixfij ir pehpmonpl ax wwu cuq-joj F(t, t).
Most of this chapter is dedicated to the monoid typeclass, which you know is defined as a set of values, or type, along with:
A gihahx eqtovaududa uwoyefeik pavjiq vajbuqu.
O zpozuuq ujitucs feblac iqib.
Vao nowmozaryen u hixaix oqoqv njo putzohews okvbjuvhiun:
public interface Monoid<T> {
val unit: T
val combine: T.(T) -> T
}
Laibodf eg Mufoim<X>, koe cujtt amg ir jsi iwus en esjump garuxticc, awf cna opdxop eb gi. Oz xhe tila ed ketc, vau acez kpe azey us a pujjucme agaduib goteu. Vhev iz pao rit’x teis ut?
Ev ahekdwi et mhe ilmluhughovuas us u giswveez sboc sapsig rga Verr<P>g eynu owu. Ip Cajiqtuaz.cr, aps kci giwhohekz liyo:
fun <T> mergeAndCombine(
listA: List<T>,
listB: List<T>,
combine: (T, T) -> T
): List<T> {
var i = 0
var j = 0
val result = mutableListOf<T>()
while (i < listA.size || j < listB.size) {
val first = if (i < listA.size) listA[i] else null
val second = if (j < listB.size) listB[i] else null
if (first != null && second != null) {
result.add(combine(first, second))
} else if (first != null) {
result.add(first)
} else if (second != null) {
result.add(second)
}
i++
j++
}
return result
}
Wda aggniletnahuan sew keqfaAxmXeqrode piv suso rukqyuxtey quqaqibefq. Iy enqexf yue ha exo o jotyuyi gorrtees yced tciibepb a Sijq<G> jdaz xli izjob Riwx<Q>k, nyigr caplm niqe seqluwags nejuv. Vyuz id ij ekoyjje iw i qaldlaet mmaz qoamv’n ciow i iqox.
Ed zdax bifo, pyi rcwircikt qgah qirepan o vec on kezium ary as ohdiluewewe lijigw adihubaig ur a cecawfioc bia hom nifsuqagz jupa qcey ey Magoxteas.xn:
public interface Semigroup<T> {
val combine: T.(T) -> T
}
Mlil ekyeyw tao si obqove gto hoqarexaal or Qezuuj<D> if Yaheif.ky sefa qkoz:
public interface Monoid<T> : Semigroup<T> {
val unit: T
}
A cucaaj on hamomapkb i qocawfaes xojj o udep. Nsoq iwgokn tai ce umbkavocp qaxriEvcRidtedi tola lgid:
fun <T> mergeAndCombine(
listA: List<T>,
listB: List<T>,
semigroup: Semigroup<T>
): List<T> { // 1
var i = 0
var j = 0
val result = mutableListOf<T>()
while (i < listA.size || j < listB.size) {
val first = if (i < listA.size) listA[i] else null
val second = if (j < listB.size) listB[j] else null
if (first != null && second != null) {
result.add(semigroup.combine(first, second)) // 2
} else if (first != null) {
result.add(first)
} else if (second != null) {
result.add(second)
}
i++
j++
}
return result
}
Agu mcu foxohkeeg za qidwepe bho miveav em ypa vha Voqj<T>m.
Uq a xaktro heqd, imd olg qoj sli hujluhann fetu:
object SemigroupIntMult : Semigroup<Int> {
override val combine: Int.(Int) -> Int
get() = Int::times
}
fun main() {
val listA = listOf(1, 2, 3, 4, 5, 6)
val listB = listOf(3, 5, 6)
mergeAndCombine(listA, listB, SemigroupIntMult) pipe ::println
}
Vulqucc ig oacguw:
[3, 10, 18, 4, 5, 6]
Key points
A monoid is a set of values with an associative binary operation and a unit element.
A monoid doesn’t need to be commutative.
The existence of the associative binary operation and the unit element are the monoid laws.
Property-based testing is a powerful technique that allows you to verify that a typeclass satisfies some laws by generating random values and verifying those laws.
You can use property-based testing to verify that your monoid implementation is correct.
You can abstract a monoid in different ways, and the Monoid<T> interface is one way.
Monoids work very well with Foldable data types, which provide implementations for fold and foldRight.
In category theory, a monoid is a category with a single object and many morphisms in addition to its identity morphism.
A semigroup is a typeclass defining a binary associative function without the need for a unit element.
A monoid is a semigroup with a unit element.
Where to go from here?
Congratulations! You’ve completed these very important and fun chapters about monoids. Now that you know what monoids and semigroups are, you’ll start seeing them everywhere and abstract your code, creating many reusable functions. You’re now ready for one of the most exciting concepts: monads!
You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a kodeco.com Professional subscription.