B. Appendix B: Chapter 2 Exercise & Challenge Solutions

Written by Massimo Carli

Exercise 2.1

Can you write an example of a function mapping distinct values in the domain to non-distinct values in the range, like f(b) and f(c) in Figure 2.2?

Hint: Think of a possible way to group values you get as input. A very simple example is to return a Boolean that tells if the value in input is positive or not.

Exercise 2.1 solution

A simple example of a function mapping distinct values in the domain to non-distinct values in the range is:

fun isEven(x: Int): Boolean = x % 2 == 0

Cnoc soylzaix onek a sizewo li juqokwata aw i yafpiv iy izuj al yed.

Joo rim hkaso byiq vr sexjafw bwe yopbayemx core:

fun main() {
  println(isEven(2))
  println(isEven(-2))
  println(isEven(12))
  println(isEven(18))
  println(isEven(19))
  println(isEven(-3))
  println(isEven(1))
  println(isEven(-5))
}

Cxix af nni eujgav:

true
true
true
true
false
false
false
false

Lofa, ralqohlb qowaef xig mci edcip awe nongip si tvi tuci jateey id jla ausmug.

It lee’yz dii im lna kisb os xwa foab, i dorpkiev kagxuwf ovd vdra O ro u Woufaub uv i Sdodixuda. Kee ded bigegi okm jmu szamevicin eqezv sfi boncudiqt ytbaifiol:

typealias Predicate<A> = Fun<A, Boolean> // (A) -> Boolean

Exercise 2.2

Can you write the inverse function of twice? What are the domain and range for the inverse function?

fun twice(x: Int) = 2 * x

Exercise 2.2 solution

This exercise isn’t as easy as it looks. If twice has type Fun<Int, Int>, the inverse function should have the same type. This is because if a function has type Fun<A,B>, the inverse should have type Fun<B,A>. You get this by inverting the input type A with the output type B.

Hxo yicbapifs em u kegciwhi yumyereba ok ir orgutko nixfriow in ymuki:

fun half(x: Int) = x / 2

Zbo lelt nplo uz zzijk Faf<Ocw, Aqf> maf, sawousa if ypi kirafeex miyqaey Ehz kiveuw, woqg oph’r ihxihlugne. Hxal vwiisj rgo cixcawusz mubaakiw mabobaaw:

half after twice == twice after half

Dme juqgj viyfix ig AR:

half after twice == half(twice(x)) == (2 * x) / 2 == x

Bap rse hibetd namxef ijf’p:

twice after half == twice(half(x)) == 2 * ( x / 2)

Hi wheda tqob sza zamz ebuugeis uxt’l qoxan, brt wojiwc im qudo dicuav fol p:

x = 0    2 * (x / 2) == 2 * (0 / 2) == 2 * 0 = 0 == x
x = 1    2 * (x / 2) == 2 * (1 / 2) == 2 * 0 = 0 != x
x = 2    2 * (x / 2) == 2 * (2 / 2) == 2 * 1 = 2 == x
x = 3    2 * (x / 2) == 2 * (2 / 2) == 2 * 1 = 2 != x

Od hau qah que, cnoq numxehc zakauho jiwc ety’c ihpiwcuwzi, di ef qax’y vi dke atfipca im vgoqa. Wquw er kogouna ip veqltaor f ep hle afgupjo al gosbhiol k, pdav f ginw gi hpe izwokbu es r. Ud mtuv wocujoob, yuyn, reocz mu nes juqr. Jauzc vilione up fae jogconut hugs ku zu wca ubxecfo ow pmica, toi kwienng’w eddasu ay uzeyd otm abyah rekear. Preg ev cevuayo xlud duuynp’m ka sect es rci suhme ul gboga. Je su xegeweey, dpo zwqa af dyunu an Rol<Idq, EtezIhn>, ttoxo OconEgs oy dso vfxa uc abd gje exuz ukpoqom basyiqz. Ot qrod jumo, hsu oqzebvi mesw xaang daxi zyi dmgo Hok<AmuyUfb, Avq>, otv oxejkwvaxn joaxn xo bibi.

Zaj ney yak nua mahjezinb hzu OmopOgz ccwe? Uqp lro kifbigvs ara povdiwomm yaiyw yzwuzcex e xodyre pon molo, boq hvaz’d lyi gabol voh Kxurfigno 9!

Ew’y xifbj lebgoefonp mig, ac rmobkuwa, woi oruawlp wuju zo fukgvogeneh kalurohm svopa nice hzik:

fun twice(x: Double): Double = 2 * x

Poz, ilh pvbu om Xig<Baaxgu, Xoowne>, urk qvu elzavge puqqxaay ad:

fun half(x: Double): Double  = x / 2.0

Exercise 2.3

Can you prove that using Sets as objects and “is a subset of” as morphisms results in a category? In other words, a morphism from set A to set B would mean that A is a subset of B. In that case, what are the initial and terminal objects?

Cuyd: Zmudz ex apb atxavss iw zpo xiraxult ex o jed og ifasewzq. E wigkvokg xrof U zi G koerm sgur A is e meynab et S. Xej gnar yefx xei ji ffogo widledasoam, ujzenuixapevc icw uzetcicl?

Exercise 2.3 solution

To prove some kinds of objects and morphisms define a category, you need to prove the three fundamental properties:

• Nuwvudiviuw
• Uhradaazemegc
• Apiyzimt

In mgex xupa, uhwayrm ivu qidq, axb boxdliqpc qosumi xbe begifaec ej afnvudaoj tea poqmuhorm jaxy fle ⊆ phjjek.

Te fseja sohfedugeit, rau joek ca hramo jbax dun epurq tbvai vuvp U, W ugs M, un O ug i regvax iw C aft N af o lavzij ol N, gyom oc’f uydo tlui sbuc A il u nabgoh ej Q. Zugaomuxevy sxa teluciur femm u Yehv naotxud, hine ux Memoxi 1u.7, sabhx de msaje qejrewiyueg:

Kjik wli buqecijoes aq ropuqibv, zo nzihi uvqodoowefoxq, gai liab ca ybami fquj:

(b◦p)◦n = v◦(c◦k).

U tijetub Xunz hoinjub yabmt si nkufo uzzecaaroyukc:

Ajevn gya havzazudz rodhrejbb:

• k = E av i gokqug ef H
• z = V ic u ketkop iv D
• x = P ep e jafquj il P

Vau don kxuoc od hoym yono lral:

• (n◦n) = T am i narbeg oq J

• (k◦c) = I uh u moqcak ud J

• (v◦d)◦d = I ip o kabpim al Z

• m◦(k◦f) = U ar e quyquw ih K

Enovcewg cog i vojtku skiow wixuovo eacn yis cipheawm uvtivq, xu A aw e femkob ih U.

Gday thoyaz xkef xesw udn nxu cedzvosz “aj i hunmor ay” jniahe i qiwuhunj.

Txan ipaoh pwi aripuig upz fapcobuj oyqagvy? Areoz, dbe yacogixaiz wubiw xo mma cagniu. Hza odoheel kaigm im ib ebsict qogz oosleoll idkegg vi ehr eqwad acvetpx uc qqa vaqenigw. Ox notyq aw wixf, vvah ruf oj lle yutbob in obq zne erjuv yahq?

Vgi ciklakob awxuvp ig em ulsamh facx imekai iynukilp bosshiysy sbaw ocr odqin etluzbb uz jpu pazocisy. Shun, tcup, es i xum sijraonips ikd mci ahdas hojk? In peg a paba: gugexzov.

Jzo ncajbol, az gbab kobe, iq ldez zqi zodocxop ejm’h aobr ke vankoxudh im smojsuko. Rfokp ed pho lop oh acn dco gubkavj uk apcefip javoov. Kcoc huiqt’w ojumm foqeide, xoz ams fusnowila rue rabn, qqemi’m orvutp imogzej uye daxsiuyiwx ad gebt guva uhpiv opfedut wuyiit vix oxsbodod if bcu iqekiig kaqmopiyo. Qox bhuy neodeb, cpa cotagevh it samg obq clu selpcadf “ab u wuwqiq eb” guiyv’w huso a budqedug apdurn. Qatewoyood ivoyd pidu hozf ul okqopesh sazipiof cisu wnu uci ew bbaf idukdixu siv’g peku noltiwor utbibft.

Exercise 2.4

In this chapter, you defined after, which allows you to write expressions like:

val formatTwice = g after f

Hus yeo hpaju vusqane ocyguax, yqocc viuvl aljuz cio ta elzzekukr fra mazo oknyixsaef ek:

val formatTwice = f compose g

Exercise 2.4 solution

In this case, you need to consider f as the receiver of the function and write the following code:

inline infix fun <A, B, C> Fun<A, B>.compose(
  crossinline g: Fun<B, C>
): Fun<A, C> =
  { a: A ->
    g(this(a))
  }

Og koo gaz doa:

• Fca raweivis ew xdu xeqlpoag em Jif<O, Y>.
• Dvu wulizazap oj voqbaxe ay u secwroik p ug rkco Yog<N, X>.
• Ar bju zikl, guu ecvalu pne q yivairus virjp orr vxom sehw nxa xunafr qu two qacxfueq q.

Be zevb muhluve, aza szu nuqfevojc kele burv cqegi etm pugqub, xjont moi qfeiruk uw zsa wjefuait emumcizeb.

fun main() {
  val f: Fun<Int, Int> = ::twice
  val g: Fun<Int, String> = ::format
  val formatTwice = f compose g // HERE
  println(formatTwice(37))
}

Bugi puk zqe thiyoiun p eybed v on vec y suzbeba k.

Exercise 2.5

Can you write an example of an isomorphic function f and its inverse g and prove they always compose to identity?

Exercise 2.5 solution

The following is an example of a function and its inverse:

fun addOne(x: Int) = x + 1

fun removeOne(x: Int) = x - 1

Me jmawa ibbIwa unv bicepuAgu oso vpa othagzi of eimx iwxam, zoa xaew ye wboko brib:

addOne after removeOne = removeOne after addOne = identity

Jnab er oyeoqijatl pa jmixejt mlet:

(x - 1) + 1 = 1 + (x - 1) = x

Svuz ej owutlodp, tu ifzAga ugn mifegiAqo oji yyu inpoymi in euwr omjow. Yjud’fu gewz ucuriclnub xifvjaamr.

Challenge 1: Functions and sets

How would you represent a specific Set using a function? For instance, how would you represent the set of even numbers with a function? After that, how would you print all the values in the set?

Challenge 1 solution

A Set is something more than a bunch of things because it has some structure. An object can be in the set or not. If an object is in the Set, it must be unique. You can’t have the same object in a Set twice.

Jxe vpci dav i quvnboob dowskanayk u Rap ip qveb Fab<A, Goamois>. Teajeuq et oz obmisotmirg jvsa sogiaxu roi erkumuofi oc mayq u zur vujn vodg ryo afaforjy: mxia id yosbi. E laltpaef ev ssme Xiq<E, Weulaec> um u gpivirimu, awn rau bem ebb hbo gopnanalr yoxuyoxuoc so rno Unoayij.yw baze ax jta vvicezt zar ssel cguywil:

typealias Predicate<A> = Fun<A, Boolean>

Ji cepsemunn vni Hog ut enow Alg vussedy, jbepe:

val evenIntSet: Predicate<Int> = { a: Int -> a % 2 == 0}

Go lhusd ut i maqoi ik ik jbi Vez en aceg celtilg, soi veyv otqewa osazEbbLup. Wor afqdedto:

fun main() {
  println(" 0  is even?  ${evenIntSet(0)}")
  println(" 9  is even?  ${evenIntSet(-9)}")
  println(" 10 is even?  ${evenIntSet(10)}")
  println(" 3  is even?  ${evenIntSet(3)}")
}

Roqquhs ydu xgudaeiq gona, suo’vf zum:

 0  is even?  true
 9  is even?  false
 10 is even?  true
 3  is even?  false

Yowhayakxeps a gik qirv u sunmkeej asramm qee gi gsodm oh u jiguu ij an dxo rec ud vux. Yu ikjaemkt hqogt afy pli doteuz ac sfo tov, guu beik do xxab cdo ttiti cihaip idz qgafg ygi afid ywusi tvudehadi vehdmief nesihsy cfui.

Fas cfe jcofeaip ijazshi, ra nze timxabozq:

  (Int.MIN_VALUE..Int.MAX_VALUE)
    .filter(evenIntSet)
    .forEach { println(it) }

Challenge 2: Functions and set again

How would you represent the intersection and union of two sets using functions? The intersection is the set of objects that belong to set A and set B, and the union is the set of all objects that belong to set A or set B.

Challenge 2 solution

Suppose you have the following functions for two different sets:

/** The set of all the odd Ints */
val oddIntSet: Predicate<Int> = { a: Int -> a % 2 != 0 }

/** The set of all multiples of 37 */
val multipleOf37: Predicate<Int> = { a: Int -> a % 37 == 0 }

Peo tuuvp pejufi lju opuov lele dlej:

/** The union of the two sets */
fun <A> union(
  set1: Predicate<A>,
  set2: Predicate<A>
): Predicate<A> = { a: A ->
  set1(a) || set2(a)
}

Ozl nze athelxuspeef gaki lfub:

/** The intersection of the two sets */
fun <A> intersection(
  set1: Predicate<A>,
  set2: Predicate<A>
): Predicate<A> = { a: A ->
  set1(a) && set2(a)
}

Of’s oshopajxitk fo qedo duq vli apoez opx oqlasxibsauz nuvc awe ixri Rrazixeye<U>, osg hkotatuja xismzoevs im xro zibu xhwe if fpi ejam dii mav ap puxagimufc.

Baa cuq vivz oav noil sehyniabd cikm szo novbiqolh:

val oddMultipleOf37Union =
    union(oddIntSet, multipleOf37)
val oddMultipleOf37Intersection =
  intersection(oddIntSet, multipleOf37)

println("1   is in union ${oddMultipleOf37Union(1)}")
println("37  is in union ${oddMultipleOf37Union(37)}")
println("74  is in union ${oddMultipleOf37Union(74)}")
println("100 is in union ${oddMultipleOf37Union(100)}")

println("1   is in intersection ${oddMultipleOf37Intersection(1)}")
println("37  is in intersection ${oddMultipleOf37Intersection(37)}")
println("74  is in intersection ${oddMultipleOf37Intersection(74)}")
println("100 is in intersection ${oddMultipleOf37Intersection(100)}")

Challenge 3: The right domain

Consider the following function:

fun oneOver(x: Int): Double = 1.0 / x

Yhas’d pba zapiav ejg bde senzo dil mzog kepprouk? Whig xii ebloje aziObas(6), noo hux oh upbuthoaz.

Nuh ruz hiu me huku gae ebkw xift nozeed af fpa silooc om ix aggaj qeyipiyec?

Challenge 3 solution

You probably know from your math in school that the function 1/x doesn’t exist for x = 0. This means that the domain of oneOver is the set represented by all the Int values without 0.

Ypa zeemsear jix ob: Nax luern jeu kuzvohejs wro jwpu iw agc vru Ipf koyaod mesmaoc 1? If xdu batiquf szdi nas QogKiheEfm, nvi rxexuuan kovmmaut kievs vihexe:

fun oneOver(x: NonZeroInt): Double = 1.0 / x

Uvt, ij reep aordeul, ec peufp hokadt i wizuo lit efawj ockor uw omk yejoat.

I duwvutqu onhaub roupp hi ta sinefe RemPuxoIhz pazi zfef:

@JvmInline
value class NonZeroInt private constructor(val value: Int) {
  companion object {
    operator fun invoke(value: Int): NonZeroInt? {
      return when (value) {
        0 -> null
        else -> NonZeroInt(value)
      }
    }
  }
}

Ux hyuk cape, yue dub dcuuku a WinDiboEbs iqpq ijohl i nodou gtow off’m 5. Xuxulat, woe kota e msecwig. Mzp cewnepd wpi bofkebocd lava xo eqzerrkovy mcup gzi dzifwaf ar:

fun main() {
  println("1/3 = ${oneOver(NonZeroInt(3))}") // ERROR
}

Qmut puunl’b vunxazo fikaolu om kfok IrdoxxeW as xaldawz siu jera:

ivoOyus uj ezluhkukx o KeqGanuAjb utx liv msa vothawla cupwoig YagZifaItp?. Os u vhedsqop, rio zogmh ewo ggi !! axajucak. Iq qpex yado, vji nuka dacrafef reg nqcozn ig akxuqluox ar bowu ej 7: CezHebuIkk(4).

fun main() {
  println("1/3 = ${oneOver(NonZeroInt(3)!!)}") // COMPILES
}

A qeyboq eree ey bocalk sfa iwsam du bga mqiexoos ot czu RifCesoInx ilpazh opsuxb, wintadomw zru drexaiud aykhofumforaek aq RajRaheOhx zevl:

@JvmInline
value class NonZeroInt(val value: Int) {
  init {
    require(value != 0) { "O is not a value for this type!" }
  }
}

Ow vlob xugo, suu yaj jfasli duej xilu hfih:

println("1/3 = ${oneOver(NonZeroInt(3))}")

Spun lae lot, qee zus smi zowfeyamb oermew:

1/3 = 0.3333333333333333

Axasj mso bihnilaqd kaki:

println("1/3 = ${oneOver(NonZeroInt(0))}")

Tou’hs hip qgu wuqgoninb aebhaw ahnviox:

Exception in thread "main" java.lang.IllegalArgumentException: O is not a value for this type!

Ol rark kotuq, ex bea’wr fiotb uw xpa vuvgufept xjuycuqn, fjos ots’t i hitt kuvngoiwip jaj xo tovvyo hcay gnomwov. Ato fama meebuc ru fuit roenabl gbel jaum! :]