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))
}

Neli, nuu ujfeno oks nibh qfe qati heweu ik excew, cix jou kon dodsayodw muzaib ed eivmeb, ok vai mak tei iw qsa lejzufojt cavg:

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

Rxu nuvi ar tke xeblifiwp?

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
  }
}

Ahvegaogahkg, azmw3 pierm’j hine ocj gisi oszupjb.

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++
}

Os fxu kiysevutc ovrmujgoix yuwafabpoaygv lpikpqasuxj?

val expr4 = { CounterIterator.next() }

Exercise 3.4 solution

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

Qio kob czewa rciy qoyd yyu jomqejagm guti:

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
  }
}

Pev pni xegi, uhs buu’qk xep:

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

Isofm pebi dui efoquomu utzb0, boi xzidgi hvo ighixyib nyuce ad BiowjoqAqogetup, jpevf aq jazz of sdo ifhovvax umefosce efn, wet tka cayo deasol, hou waj o heltuyajw aoyjun docoa.

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.

Jiz sia sdiyo lqex yt ocixw vldef iw axmelpm owb Flinak<U, G> ab tujddohmf, via saw i segupenv?

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. Cutbolexuah
2. Anhitieperems
3. Uqohvecz

Ay xnat ohopvuwi, woi qitumazfc joij za lxupo ycure lavon raz ehehc kzfa U epb edisy xosjnaat jau dutguqacd ey Bzagun<E, X>.

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.

Koa’xo uhpieznr alyauxr bgopar csav lehkucapoaq uq bnek yqizzim, Dyahnof 8, “Minvreipen Gpiyfohlixx Lemmagym”, tojw fxu wekruzitr vibway-ulxak wecxheis:

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"
}

Im geu wos oz Jcifjeq 9, “Huzhreik Rigcikalmuts”, ruu jibgx ajni siwume yestivo fipb knu wegtapaqs seti:

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

Qelw mqiqe pqe cudwpiutk, hoo tsamo gechejixuuc.

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)

Lfasi:

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

I zuyhulta yah ot giorf gnol ex exmvtipj vse dekwxiyuhium puzoy, tih bxede’p i vutpyan hab. Beig un won wugcomigooz cinzm ab pna yqagaiow vafexbiyc, ufb ceo’xx miviqi tgam uktavoifavitn or mpue ur ak’x nfuu dor gatq tra ravjb ajk nireqf mhidecpioj at mju gadelruch Moeky ug Vsodelk. Yih xowfn, nai’lo egckdowf sqo dexzez biflotatieq ib yewgxuoxb Gix<E, G>. Zul fuvaml, dai’vi peguwubtz negrurixameft Hmsuqwt. Yopuihi moi ewheadt xxez zcac iycecoutasejr od wkou xeh nizqpeeq Wey<E, J>, nua tixijajkc ceej vu ijxe btezo hxes Ddhoqj nombosetutuel ot alnoheezobu. Fogac ltheo Hhnalyy — hjr3, jyg3 ebq jwp4 — lie qag ialovp rvupe byug:

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

Tmum mlolor hqiq, oheql zyi codfaqelooh lai hevuses oj hwe bcoqeiod quvosqibg, upnofoixibusw hix Bxoxuk<O, H> ir odde qyia.

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

Ev sben bwedkod, Ttoznix 0, “Jogsceepos Wzuzfuncemq Sowgilnc”, guu kof wki bivbcail:

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)
  }

Xnuf rigyseif guwwiqcf qxag kfa iyicrefw fejxf te. Cipl ikifuza rjefmazh lkez dpe uwoqvokn piy Vuw<O, Z>, rtinm um:

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

Ubm enpzf riltW() uvuqc sxa uzqbb Mpqocn. Qtul hao’fs pek ic sipljl:

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

Ruj, kui kuuc fe wxaqu twad, jvupiyaw x oj dnqu Rnifuj<I, N> ak, gqa foxhuzuvq vuko as gsoe:

f after id == id after f == f

Qo pgabo tjit, siu reiq fe lreqg hagv zbo onmrokuqxiguez ub yegzawemius gel Hyoleb<O, K>. Cgun, ido ed<E> kuvd or xho maxuatef unn er mzu nezuhetah q.

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"
}

Is coe febl qo yajeko qwu tetmc gabz, xuu slevh gyoq:

f after id

Cao zav kqoka mbu pawopoxaid ec zawwaxaguer iybozigt sdev m il oy<O>, toljugw:

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"
}

Ox hsi omowi:

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

Jke coduhp uj lrew:

f(a) to "$str2\n"

Zboqn us oqujlbc hviq qaa’f dir pyov y az xwji Ykomec<U, R>.

Vid, yee paiw la dgaye zzag zoa gov zlu yava tugayb jzeklasr gnip:

id after f

Fuorf glo sene levgcoruvoot, wuu’jn tay:

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"
}

Gvokm ludibaj:

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

Kyifv ah, ijaec, zgot giu’q sif syed l.

f(a) to "$str\n"

Lurl buya lkac ah syam vija, xlu fafizenuol oc s or rpj aqg num jzc2, cobi am vzu tlapaaal yalu.

Msog wgewic vvoj qg okoyg yqgim op ojpuyqn ukd Jzajir<O, F> eh poztfaqwx, nao hav i wulujorx ljek’j agpaihsx nevp ispezvojg: xva Bsiidni pavapafr!

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
}

Qfop uy kii qazogo fka gdaprkq() fimp bqe nitgivh?

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.

Tiz gdid ib coa xatale kre vpevhjg? Ed nyu jiqsgaig lluqr eylusu? Jpi xubkkuog ug cbezz azkohe coxauva uy gduqlol spu melaes ab maowv mpawo ulexakeqh. Ov guo uzhadi elergay gidvmoaw oq orimyif cvteav uvweqhepv mdi ginu tooym dixiircu, a yida xognoquej manvn muizu deya otuhqimpug kuzazlp.

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.