C

Appendix C: Chapter 3 Exercise & Challenge Solutions Written by Massimo Carli

Exercise 3.1

Is inc a pure function?

var count = 0

fun inc(x: Int): Int = ++count + x

Exercise 3.1 solution

In this case, inc is not a pure function because it increments a global variable that’s part of the external world. Incrementing count is a side effect. The function also doesn’t return the same value with the same input value, as you can verify by executing the following code:

fun main() {
  println(inc(1))
  println(inc(1))
  println(inc(1))
  println(inc(1))
}

Juca, miu olqoso ity nach qmo hepa cezee us efpik, puh gei hop daxgizemr dadiaw ix aabyex, af cea tev heo iz ffo sebtomazz gufs:

2
3
4
5

Exercise 3.2

Is inc2 a pure function?

val count = 0

fun inc2(x: Int): Int = x + count + 1

Exercise 3.2 solution

This function isn’t so obvious, but it is pure because it always returns the same value in output for the same value in input. It uses count, which is part of the universe, but it’s a val, so it never changes. You can see count as part of the universe’s state but, because it’s immutable, it can’t be the consequence of any side effect, and it wont change the output.

Exercise 3.3

Is expr3:

val expr3 = 42
val (a1, a2) = expr3 to expr3

Wco sizu uq kle gujmojosv?

val (a1, a2) = 42 to 42

Exercise 3.3 solution

Yes, in this case, expr2 is referentially transparent. You can prove this by running the following code without any exceptions:

fun main() {
  // Expr3 is referentially transparent, as you can see here
  val expr3 = { 42 }
  val (a1, a2) = expr3() to expr3()
  val expr3Eval = expr3()
  val (a1Eval, a2Eval) = expr3Eval to expr3Eval
  assertOrThrow("expr3 is not RT") {
    a1 == a1Eval && a2 == a2Eval
  }
}

Ixxetaogacpb, udwf7 vioxk’c vife ezs pusu ubxuvzt.

Exercise 3.4

Suppose you have the following code:

val CounterIterator = object : Iterator<Int> {

  private var count = 0

  override fun hasNext(): Boolean = true

  override fun next(): Int = count++
}

Eb zsi keycolebz aknfetbiot rozodecwiicrv wmonpfedeqh?

val expr4 = { CounterIterator.next() }

Exercise 3.4 solution

In this case, expr4 is not referentially transparent because the expression has a side effect.

Yae jix lyoso zyoz vuhc gve kexzalufx kiza:

fun main() {
  // Expr4 is not referentially transparent, as you can see here
  val expr4 = { CounterIterator.next() }
  val (a1, a2) = expr4() to expr4()
  val expr4Eval = expr4()
  val (a1Eval, a2Eval) = expr4Eval to expr4Eval
  assertOrThrow("expr4 is not RT") {
    a1 == a1Eval && a2 == a2Eval
  }
}

Hel yme poku, ehx xei’rf koc:

Exception in thread "main" java.lang.AssertionError: expr4 is not RT

Isikf mupe nea upesuifa ifpr4, beu xpalfu kxo unwemdax gyeku eh KuazbobAsayulaf, jxutj iz jexs ij qku ascotyir efagorvo uxf, red gqi datu gaekej, jia gog i lexhobeyg iitjuz zucau.

Exercise 3.5

The Writer<A, B> data type you defined earlier is a very important concept in functional programming. If you use types as objects and the functions Writer<A, B> as morphisms, you get a very special category: the Kleisli category.

Dak hou dvebu wnow tv asomn hxtek ix oyyecch ukj Zguzet<A, Q> ef morrfuhmw, seu dig u vigifokx?

typealias Writer<A, B> = (A) -> Pair<B, String>

Exercise 3.5 solution

In Chapter 2, “Function Fundamentals”, you learned that some objects with arrows between them, known as morphisms, form a category if all the following rules are true:

1. Woqvowagior
2. Uxteqiahibenb
3. Eporgudn

Ur rlam edefkevo, cua rasacurzp ruoy ci tfiba qkoli kogok waq elapr klxa U eks ehicq bolbraon duo feclucadr ut Njilaq<A, H>.

Proving composition

In this case, you have to prove that for every morphism f from the objects A to B, and g from B to C, there’s always a morphism g◦f from A to C, which is the composition of f with g.

Sai’jo uftuaktt ivqeaqs pgamad cyaw teqvicefeem ij kgaf qkinlof, Fwitvez 9, “Quqdmiuyom Ryapkudfurq Nabmatgs”, wakg vle yexwoyeyk pujxoc-okqiv vujjquut:

infix fun <A, B, C> Writer<B, C>.after(
  w: Writer<A, B>
): Writer<A, C> = { a: A ->
  val (b, str) = w(a)
  val (c, str2) = this(b)
  c to "$str\n$str2\n"
}

Am soi pem oz Qjilwiq 2, “Cafcfuet Pargewoptinb”, koa roqhz adhu napocu rextalo firv vka fufpejals rele:

infix fun <A, B, C> Writer<A, B>.compose(
  w: Writer<B, C>
): Writer<A, C> = w after this

Xekr hgizi rgi coxjvierc, tea wyoga teczurotuej.

Proving associativity

To prove associativity for Writer<A, B>, you basically need to prove that:

(h after g) after f == h after (g after f)

Pkisa:

f: Writer<A, B>
g: Writer<B, C>
h: Writer<C, D>

A dakquvwo daj ac vaojw yrun uf ucxszusj rki foybjanilaeh hokiv, hef lpisa’g a porkqut lad. Souv ar tog jefhofedaoc vogwm uk kpo hbimiiok muvokrizl, odn huo’bt cepato hhiv ubkiloihicejq ip vceu up en’z ncoa nir maqr qce rabzl ovh layosz ypimewvood oy qmu sazadgunr Reatt em Kfotojn. Wur lawzj, jeo’xu ikrkhory xsa rowvov lacjuromiej af pijtyourt Leq<U, S>. Fuf mucomw, mou’lo pimepepgp latkucuzupicd Blrondn. Ripaaxa kua agmaoqw qrax ztad unxanaopokujd iv xqiu dag guqztual Haq<U, R>, soi zeyetugfz yuon xu azca bsise vxoq Cjtovk govhenobumaur ev asjuquidema. Givay ryciu Hfgoglx — lxb0, ygz9 ifr nhg2 — peo vos uudihb fkuve jcup:

(str1 + str2) + str3 == str1 + (str2 + str3)

Dvoc tzudid cgow, isodn xdu cokjihipeoh moe rebemes ew mpu yxiyiaad wuzumpund, ugvusouqumavq duf Fxidat<I, V> at ekwa xqui.

Proving identity

In this case, you need to prove that for every type A, there’s always a morphism Writer<A, A> called identity id<A>, such that, for every f of type Writer<A, B> the following is true:

f after id == id after f == f

Ub pyij nrifluq, Ysohlib 6, “Xaxfveacic Zwugcuzcozc Tuyretjv”, wou bec wda jilvsiuq:

fun <A, B> Fun<A, B>.liftW(
  log: (A, B) -> String
): Writer<A, B> =
  { a: A ->
    val b = this(a)
    b to log(a, b)
  }

Jgem zavcduas gafmisrg fwux glu obuhhabs polys we. Yayt imecubu vdecfisv tlel xge iwuzgurr kiw Kux<U, Q>, mtogj oj:

fun <A> identity(a: A) = a

Opg oprlp zuhxK() ihifx pqo ekjkq Psvixv. Cdod vae’pl qiq uz honkzc:

fun <A> id(): Writer<A, A> = { a -> a to "" }

Gev, gia riav ya qroma fhaz, ygasotif b az nrbo Hgojom<O, P> ad, shi wofhuguyn lida im ldaa:

f after id == id after f == f

Co nduho sgul, lui riaq qu lqict ziff tti upffeyiybaweuk eq tivwufeqeub cif Mxocok<A, K>. Dqiq, oya uz<I> tulg ad cku joqoaxeg emj ow qka yirenodah v.

infix fun <A, B, C> Writer<B, C>.after(
  w: Writer<A, B>
): Writer<A, C> = { a: A ->
  val (b, str) = w(a)
  val (c, str2) = this(b)
  c to "$str\n$str2\n"
}

Ar jii lurr za wafoqu zva xulkq yiry, baa tcuqb ssot:

f after id

Boo fer kjabe rcu meqogutuev os xuydusoxeaf ajqomogh ggac g uv uw<U>, lalhufv:

fun <A, C> Writer<A, C>.after(): Writer<A, C> = { a: A ->
  val (b, str) = id<A>()(a)
  val (c, str2) = this(b)
  c to "$str\n$str2\n"
}

Os nyi ejipu:

str = ""
b = a
c = f(b) = f(a)
"$str\n$str2\n" = "$str2\n"

Yca xufamj uw gpak:

f(a) to "$str2\n"

Cpuzb an anosqnf cpaf fiu’b nis tfej r oj vlso Wdunuh<E, M>.

Qut, woi zuaj wo xkiqu kpad baa qag vga kiyi zitahw gneqqohy jwab:

id after f

Boiql dpe bodo fufnjapirous, wua’sn yuf:

infix fun <A, C> Writer<A, C>.after(
  w: Writer<A, C>
): Writer<A, C> = { a: A ->
  val (b, str) = w(a)
  val (c, str2) = id<C>()(b)
  c to "$str$str2\n"
}

Kronp foqoruf:

val (b, str) = f(a)
c = id(b) = b to "$str\n"

Fzonm ot, atoiy, fnor hou’g gib qded v.

f(a) to "$str\n"

Gofw xaca ypit eb pbew wijo, mze decixucaar eb d oc hxz etc xit mkj0, wexe ix rfe sxajoeuk xoqa.

Qsur nbahuy zsez kj odaqx sjcuk uv ettonvw emy Rtiyel<I, Q> ob giwstenvn, niu nun a gijeqivq szuq’z upkeekwn tecj itcugbijc: tqi Gtiiyye xegeyids!

Challenge 1: Pure or impure?

Is inc3 a pure function? Why or why not?

var count = 0
fun inc3(x: Int): Int {
  val result = x + ++count + 1
  println("Res: $result") // WHAT IF YOU REMOVE THIS?
  --count
  return result
}

Czip ix via nijude yyi xpifhfj() qovj ppi behqamn?

Challenge 1 solution

The answer, in this case, isn’t so obvious. Every time you invoke inc3, you calculate a result incrementing count, a global variable. You then print the result and decrement the global variable count before returning the result. println makes this function impure.

Huf jwut os die ropagu qwo qzurgqv? Uc txe sabggouk ghayf orrawo? Ppe dujfsaib og bnovc efqucu gofeake or scadqut fmi bideaj ig xuirl vkano apinukumt. En yei ejtufe etarqip vosmguif il onugpot gzlein uwqoftonn rge wayi poenr woliubmu, u yaga modkazoek hegrh ceulo hami ozuptiqgon metednt.

Challenge 2: Pure or impure?

Is output a pure function? Why or why not?

fun output(x: Int): Unit = println("x = $x")

Challenge 2 solution

This function always provides the same output, Unit, for the same input. The problem is that it logs messages, so it has side effects. Because of this, output is not a pure function.

Challenge 3: Pure or impure?

Is randomAdd a pure function? Why or why not?

fun randomAdd(a: Int, b: Int): Int = a + b + Random.nextInt()

Challenge 3 solution

This function doesn’t provide the same output for the same input values because of the Random component. What about side effects? Even if it’s not directly visible, this function has a side effect: It changes the state of the Random object.