# 4 Expression Evaluation, Laziness & More About Functions Written by Massimo Carli

In the previous chapters, you learned that you can define a function as “a bunch of code that might be executed later”. You also learned several interesting points:

• As a software engineer, you write code and, more specifically, you write functions.
• If the functions you write are pure, their bodies are referentially transparent expressions.
• Executing a function means evaluating the expression in its body.
• “Executed later” means the expression of a function is evaluated at a time that isn’t related to the position of the expression itself.
• It’s possible that a function is never executed and the expression never evaluated.

Evaluation strategy is the relationship between the position where you define the expression in your code and the point when the expression is actually evaluated. In this chapter, you’ll learn about two different evaluation strategies:

• Applicative-order evaluation
• Normal-order evaluation

These two evaluation strategies will lead you to other very important concepts in this chapter:

• The evaluation strategy for Kotlin.

• What strictness and laziness mean.

• How lambda expressions allow you to execute your code later.

• The Kotlin lazy function and how to use it to improve performance.

• How to implement memoization for pure functions in Kotlin.

• How to implement infinite `Stream`s of data using lazy functions.

Again, all this uses Kotlin and many engaging exercises and challenges. Open up the starter project for this chapter to begin!

## Expression evaluation order

As you know, you can write a pure function and execute it much later. Here’s an example to help you understand how the position of an expression relates to the time it’s evaluated.

Suppose you want to evaluate the following expression that calculates triple the average of two values:

``````3 * avg(x, y)
``````

To represent this expression as a function, write the following code in the initially empty Evaluation.kt file in this chapter’s material:

``````fun add(x: Int, y: Int): Int { // 1
val result = x + y
return result
}

fun triple(x: Int): Int { // 2
println("triple") // 5
return result
}

fun divide(x: Int, y: Int): Int { // 3
val result = x / y
println("divide") // 5
return result
}

fun average(x: Int, y: Int): Int { // 4
val result = divide(add(x, y), 2)
println("average") // 5
return result
}
``````

In this code, you:

1. Create `add`, which returns the sum of the two input values.
2. Define `triple`, which uses `add` twice. This is possible because addition is associative, as are pure functions. You also know that pure functions and types create a category, which has associativity by definition.
3. Implement `divide`, which returns the division between the two input values. This is a division of `Int`s, so the result will always round down to a whole number. In this context, the precision of the function doesn’t really matter, so that’s OK. :]
4. Create `average`, which uses `divide` and `add`.
5. All these functions would be pure, but you added some `println` just to understand how and, more importantly, when they’re evaluated. It’s important to note how `println` follows the evaluation of the expression, giving evidence of the actual execution.

Now, write and run the following:

``````fun main() {
triple(average(2, 4))
}
``````

You get the output:

``````add
divide
average
triple
``````

At first glance, you see that `triple` is the function evaluated last.

To understand why, apply the substitution model like this:

``````triple(average(2, 4)) // 1
triple(divide(2+4, 2))
triple(divide(6, 2)) // 3
triple(6/2)
triple(3)
6+3
9
``````

In the previous representation, you see that you always reduce the expression that allows you to give the leftmost function all the value it needs. In particular:

1. To resolve `triple`, Kotlin needs to resolve the expression you pass as an input parameter: `average`.
2. Next, you need to evaluate and give `divide` the value it needs as input: the sum of `2` and `4`. This is why Kotlin evaluates `add(2, 4)` first.
3. At this point, `divide` has all the values it needs, and Kotlin starts the `divide` evaluation.
4. It’s now time to evaluate `triple`, which needs to evaluate the `add` you have as the first input parameter.
5. Finally, you reduce everything to the value `9`, which you can see by printing the result of the expression using this code:
``````fun main() {
val result = triple(average(2, 4))
println(result)
}
``````

The previous example proves that in Kotlin, a function’s arguments are evaluated before the function is applied, which is the definition of applicative-order evaluation. With applicative-order evaluation, a function executes only when all the expressions you pass as input parameters are evaluated, starting from the leftmost parameter.

Note: Another name for Kotlin’s applicative-order evaluation is eager evaluation.

But is this evaluation strategy good or bad? How would the same expression be evaluated in the case of normal-order evaluation, and what would the advantages be? Before exploring that, it’s important to see some more examples.

### Applicative-order evaluation examples

You just learned what applicative-order evaluation is, resolving a simple expression in Kotlin. To better understand what the consequences are, open the initially empty ApplicativeOrder.kt and write the following code:

``````fun greaterThan10(x: Int): Boolean { // 1
println("greaterThan10") // 2
return x > 10
}

fun main() {
val inputValue = 3
if (inputValue > 4 && greaterThan10(inputValue * 2)) { // 3
println("OK") // 4
} else {
println("KO") // 4
}
}
``````

In this code, you:

1. Define `greaterThan10` as a simple function returning a `Boolean` stating whether the input value is greater than `10`.
2. Use `println` to give some evidence of the invocation of `greaterThan10`.
3. Define a simple test to check if the value of a local `inputValue` variable is greater than `4` and whether the result of `greaterThan10` passing `inputValue * 2` as input is `true`.
4. Print `OK` or `KO` if the test is `true` or `false`, respectively.

Run the previous code, and you’ll get:

``````KO
``````

This is because `inputValue` isn’t greater than `4`. The interesting part is that `greaterThan10` wasn’t even invoked. The reason is the use of `&&`, which is a short circuit operator. When you resolve `A && B`, a `false` value of `A` makes the whole expression `false` and the evaluation of `B` would be irrelevant.

Note: The same is true with the `||` operator. In the case of `A || B`, a `true` value for `A` would make the whole expression `true`. The evaluation of `B` would then be irrelevant.

Now, change the previous example like the following, assigning `30` to `inputValue` and passing it to `greaterThan10`:

``````fun main() {
val inputValue = 30 // HERE
if (inputValue > 4 && greaterThan10(inputValue)) {
println("OK")
} else {
println("KO")
}
}
``````

Run the code and find:

``````greaterThan10
OK
``````

In this case, `inputValue > 4` evaluates to `true` and `&&` requires the evaluation of `greaterThan10(inputValue)`. This is why you see `greaterThan10` as part of the output.

So far, so good. This is how `&&` works. Now, change the previous code like this:

``````fun main() {
val inputValue = 3 // 1
val greater10 = greaterThan10(inputValue) // 2
if (inputValue > 4 && greater10) { // 3
println("OK")
} else {
println("KO")
}
}
``````

In this case, you:

1. Use `3` as the initial value for `inputValue`.
2. Invoke `greaterThan10`, passing `inputValue` as input.
3. Use `greater10` in the condition for `if`.

This is equivalent to the very first example but, when you run the code, you get the following output:

``````greaterThan10
KO
``````

The output contains `KO`, but `greaterThan10` has been invoked anyway. This might look obvious because you evaluate `greaterThan10` before the test, and you don’t know yet if the `if` condition would require it or not.

However, is it possible to define the invocation of `greaterThan10` in the same position as the last example but then execute it when you actually need it? The answer is yes, using lazy evaluation with lambda expressions.

## Understanding lambda expressions

A lambda expression is simply an anonymous function you can use as a value. This basically means that:

• You can define a lambda expression on the fly, assigning it to a variable.
• As you’ll see in detail in Chapter 5, “Higher-Order Functions”, you can use a lambda expression as an input parameter or the result value of another function.

You define a lambda expression by adding a normal expression in a code block. The following is a perfectly valid lambda expression you can find in Lambdas.kt in this chapter’s material.

``````val empty = {}
``````

In the case of an input parameter, you define a lambda expression like the following:

``````{ a: Int, b: Int -> a + b }
``````

In this case, you create an anonymous function that returns the sum of two input parameters of type `Int`. The result of evaluating a lambda expression is the value of the last expression in its body, in this case, the sum of `a` and `b`. You separate the input parameters list and the result expression with `->`. It’s important to note that both the input parameter and the result expression are optional, as you saw in the first example.

Exercise 4.1: Can you write a lambda expression that calculates the distance between two points given their coordinates, `x1, y1` and `x2, y2`? The formula for the distance between two points is `distance = √(x2−x1)²+(y2−y1)²`.

Give it a try, and afterward, check the solution in Appendix D or this chapter’s challenge project.

### Lambda type inference

Type inference is the mechanism a compiler uses to understand the element types involved in an expression.

When the compiler can’t get all the information it needs about types, you’re supposed to help. You can give the compiler the information it needs in different ways. In the previous code, you helped the Kotlin compiler by adding explicit type information for `a` and `b`. The Kotlin compiler then understands that `a` and `b` are `Int`s, and the result of the lambda expression will also be `Int` because of the type of the result of `a + b`.

The following code would give a compilation error because the Kotlin compiler wouldn’t know the types for `a` and `b`.

``````val lambda = { a, b -> a + b }
``````

You can use a lambda expression as a normal value. This means you can assign it to a variable, like in the following example:

``````var operation = { a: Int, b: Int -> a + b }
``````

In this case, you assign a lambda expression to a variable `operation`. The compiler infers for `operation` the type `(Int, Int) -> Int`, which is the type of any function with two input parameters of type `Int` returning another `Int`. Another way to give the compiler the information it needs is:

``````var operation: (Int, Int) -> Int = { a, b -> a + b }
``````

By defining `operation` of type `(Int, Int) -> Int`, you’re telling the Kotlin compiler the type of values you can assign to it. Because `{ a, b -> a + b }` is compatible with the type of `operation`, the compiler infers an `Int` type for `a` and `b` and also verifies the return type. In this case, the Kotlin compiler inferred the type of the input parameters `a` and `b` from the type of `operation` you defined explicitly.

Exercise 4.2: What’s the type for the lambda expression you wrote in Exercise 4.1?

Again, give it a try and check the solution in Appendix D or the challenge project.

The type of a lambda expression is then a function type, meaning the following code is perfectly legal:

``````typealias Fun<A, B> = (A) -> B

val multiplyBy2: Fun<Int, Int> = { x -> 2 * x }
``````

Exercise 4.3: What are the types of the following lambda expressions?

``````  val emptyLambda = {} // 1
val helloWorldLambda = { "Hello World!" } // 2
val helloLambda = { name: String -> "Hello \$name!" } // 3
val nothingLambda = { TODO("Do exercise 4.3!") } // 4
``````

Can you write an example of a lambda expression of the following type?

``````typealias AbsurdType = (Nothing) -> Nothing
``````

In this case, can you show how to invoke it?

Try to answer without the support of IntelliJ, and check your solutions in Appendix D or the challenge project.

### Lambda expression evaluation

A lambda expression allows you to define an expression without actually resolving it. Consider the following definition:

``````var operation = { a: Int, b: Int -> a + b }
``````

Here, you’re defining a lambda expression that describes how to calculate the addition of two `Int`s, but you’re not actually running it. This is the beauty of lambda expressions: They allow you to describe code you’ll execute later with the advantage that you can treat them as data. You can handle the value `2` and the lambda `operation` as values exactly the same way. You can treat them as input parameters and return values of functions.

Eventually, you might need to execute or resolve the lambda expression. How can you do that? And, in that case, what would the final result be?

As mentioned earlier, a lambda expression is a function type. This means you can execute it like any other function. For instance, in the previous example, add the following to Lambdas.kt:

``````fun main() {
val result = operation(3, 4)
println(result)
}
``````

Running this code, you get:

``````7
``````

You can achieve the same thing using `invoke` like this:

``````fun main() {
val result = operation.invoke(3, 4)
println(result)
}
``````

The value you get resolving a lambda expression is the value of the last expression in its body. Consider the following code:

``````val testLambda = { a: Int ->
val doubleA = a * 2
if (doubleA > 10) "\$doubleA is Greater than 10"
else "\$doubleA is Smaller or Equal to 10"
}
``````

In this example, the `if` expression is the last in the body of `testLambda`.

You’ll see much more about lambda expressions in the following chapters of this book. Here, it’s helpful to provide some useful and interesting information about:

• Lambda type inheritance
• Generic lambda expressions

#### Lambda type inheritance

In the previous paragraphs, you learned that the type of a lambda expression is a function type. In Chapter 2, “Function Fundamentals”, you learned that a type is a way to represent the set of all possible values. For instance, with `Int`, you represent the set of all the possible integer values — or, at least, the ones you can represent in Kotlin. When you define `operation` like this:

``````var operation: (Int, Int) -> Int = { a, b -> a + b }
``````

What are the actual lambdas you can assign to it? Only the ones of type `(Int, Int) -> Int`? In this case, the answer is yes. You can only assign functions of that type to `operation` because `Int` is final, but this isn’t always the case.

Note: Saying that `Int` is final means the `Int` class can’t be extended.

Suppose you have the following types:

``````class A
class B
``````

Now, suppose you define the following function type:

``````typealias LambdaType = (A) -> B
``````

`LambdaType` is the type of generic function from `A` to `B`. This means you can write the following code, which is perfectly legal:

``````var lambda: LambdaType = { a -> B() }
``````

Now, suppose you have the following new types:

``````class C
class D
``````

What relation do these new types need to have with the previous `A` and `B` to make the following definition valid?

``````lambda = { c: C -> D() }
``````

At the moment, the compiler is complaining because `C` isn’t an `A` and `D` isn’t a `B`. You basically need to make the function type `(C) -> D` a subtype of `(A) -> B`.

To fix this, you need to create the following relations you can visualize in Figure 4.1:

``````class A : C()
open class C
class D : B()
open class B
``````

This means `LambdaType` is contravariant for the input type and covariant for the output type.

Note: Variance is a crucial concept when working with generic types. Given a hierarchy relation between two types, `A` and `B`, it describes the relation between `F<A>` and `F<B>`. Here, `F` is a data type you represent using generic types like `List<T>`, `Set<T>` and others. Using this terminology:

You have covariance when given `B` IS-A `A` entails that `F<B>` IS-A `F<A>`.
When given `B` IS-A `A` entails that `F<A>` IS-A `F<B>`, you have contravariance.
When given `B` IS-A `A` entails nothing about `F<A>` and `F<B>`, you have invariance.\

To give a quick example, if `Triangle` IS-A `Shape` entails that `List<Triangle>` IS-A `List<Shape>`, you say that `List<T>` is covariant.

#### Generic lambda expressions

You might be wondering about the difference between a normal function and a lambda expression. For instance, what’s the difference between the function:

``````fun add(a: Int, b: Int): Int = a + b
``````

And the following lambda expression?

``````val sum = { a: Int, b: Int -> a + b }
``````

Well, in this specific example, there’s no difference — but consider the following case instead:

``````interface Combinable<A> { // 1
fun combine(rh: A): A
}

fun <A : Combinable<A>> combine(lh: A, rh: A): A = lh.combine(rh) // 2
``````

In this case, you define:

1. The `Combinable<A>` interface, which defines `combine`. `combine` returns the combination of two objects of the same type `A`.
2. The `combine` function, which appends two input `Combinable<A>` objects into another `Combinable<A>`. This is a generic function in the type `A` with the constraint of considering only `Combinable<A>` objects.

How would you represent `combine(lh: A, rh: A)` using a lambda expression? Unfortunately, the following definition wouldn’t work:

``````val combineLambda = { lh: A, rh: A -> lh.combine(rh) } // ERROR
``````

You can’t define a generic lambda expression the same way you do for a normal generic function. You might try to solve this problem with the following code:

``````typealias CombineLambdaType<A> =
(Combinable<A>, Combinable<A>) -> Combinable<A> // 1

val combineLambda: CombineLambdaType<A> =  // 2
{ lh: A, rh: A -> lh.combine(rh) } // ERROR
``````

In this case, you:

1. Define the typealias `CombineLambdaType<A>` as a function from two `Combinable<A>` to a single `Combinable<A>`.
2. Use `CombineLambdaType<A>`, trying to infer the parameter type to the lambda.

This doesn’t work because you wouldn’t be able to set the constraint on the type `A`.

In short, you can’t define a lambda expression on a generic type. This is why expressing `combine(lh: A, rh: A)` using a lambda expression won’t work. It’s the consequence of the fact that lambda expressions are like values, and you can’t define a value of a generic type `A`.

## Lazy evaluation

Now that you know almost everything about lambda expressions in Kotlin, you can return to the following example you already wrote in ApplicativeOrder.kt. Next, copy it into LazyEvaluation.kt, using the same `greaterThan10`:

``````fun main() {
val inputValue = 3
val greater10 = greaterThan10(inputValue)
if (inputValue > 4 && greater10) {
println("OK")
} else {
println("KO")
}
}
``````

As you remember, if you run the code, you get:

``````greaterThan10
KO
``````

How can you keep the same layout and evaluate `greaterThan10` only when you really need to? Now you know the answer: Use a lambda expression. Just replace the previous code with the following:

``````fun main() {
val inputValue = 3
val greater10 = { greaterThan10(inputValue) } // 1
if (inputValue > 4 && greater10()) { // 2
println("OK")
} else {
println("KO")
}
}
``````

In this code, you:

1. Replace `greaterThan10` with a lambda expression you saved in `greater10`.
2. Invoke `greater10` only if necessary.

Run the code, and you get:

``````KO
``````

Running the same code after changing `inputValue`’s value to `30`, you get:

``````greaterThan10
OK
``````

What you implemented using a lambda expression is called lazy evaluation. Lazy evaluation means resolving an expression only when you actually need it.

Exercise 4.4: Can you implement a function simulating the short-circuit and operator with the following signature without using `&&`? In other words, can you replicate the short-circuiting behavior of `left && right`:

``````fun shortCircuitAnd(left: () -> Boolean, right: () -> Boolean): Boolean
``````

Can you also write a test to prove that `right` evaluates only if `left` is false?

Try to answer without the support of IntelliJ, and check your solutions in Appendix D or the challenge project.

### Kotlin lazy delegate

Kotlin allows you to implement lazy evaluation using the… lazy delegate. :] Before understanding how `lazy` works, it’s useful to look at the `by` keyword. The Kotlin keyword `by` allows you to control the access to a variable, delegating getters and setters to the object you use as the target of the delegation: the delegatee. You call this property delegation.

To understand how it works, write the following code in Lazy.kt:

``````fun testDelegate() {
var variable by object { // 1

var localInt: Int? = null

operator fun getValue( // 2
thisRef: Any?,
property: KProperty<*>
): Int? {
println("Getter Invoked returning \$localInt")
return localInt
}

operator fun setValue( // 3
thisRef: Any?,
property: KProperty<*>,
value: Int?
) {
println("Setter Invoked with value \$value")
localInt = value
}
}
variable = 10 // 4
}

``````

In this code, you:

1. Use `by` to delegate `variable`’s access to a generic object.
2. Implement `getValue`, which is invoked every time you access `variable`.
3. Implement `setValue`, which is invoked every time you set a value to `variable`.
4. Assign the `10` value to `variable`.
5. Access `variable` and print its value.

This is why, running `testDelegate()`, you get the following output:

``````Setter Invoked with value 10
Getter Invoked returning 10
``````

Now that you know how `by` works, just write the following code:

``````fun main() {
val inputValue = 30
val greater10 by lazy { greaterThan10(inputValue) } // 1
if (inputValue > 4 && greater10) { // 2
println("OK")
} else {
println("KO")
}
}
``````

In this code, note that you:

1. Use the Kotlin keyword `by` to delegate the access to the `greater10` variable to the object you get by invoking `lazy`. You pass to `lazy` the lambda function you want to eventually execute for `greater10` initialization.
2. Just access `greater10` in the `if` condition.

Running the previous `main`, you get:

``````greaterThan10
OK
``````

Change the `inputValue` to `3`, and you get:

``````KO
``````

This is what you’re expecting, but `lazy` gives you something more. Add the following code to Lazy.kt:

``````fun multiLazy() {
val multiLambda by lazy { println("I'm MultiLambda") }
multiLambda
multiLambda
multiLambda
multiLambda
}
``````

In this code, you:

1. Use `lazy` with a lambda expression containing the `println` of a message.
2. Access `multiLambda` multiple times.

When you run `multiLazy`, you get:

``````I'm MultiLambda
``````

This is cool! The lambda expression you pass as a parameter to `lazy` is evaluated just once, and its result is reused when accessed again.

Of course, in this example, you use a `println` to prove that behavior, but if it doesn’t have any side effects or the expression takes some time, `lazy` is very useful. In this way, you achieved memoization, which you’ll learn about next.

Exercise 4.5: Can you implement the function `myLazy` with the following signature, which allows you to pass in a lambda expression and execute it just once?

`````` fun <A: Any> myLazy(fn: () -> A): () -> A // ???
``````

Try to answer without the support of IntelliJ, and check your solutions in Appendix D or the challenge project.

## Memoization

In the previous chapter, you learned that a pure function always produces the same result for the same input values, a concept known as referential transparency. A pure function also doesn’t have any side effects, and this makes it idempotent. Because of this, you don’t need to run the same pure function multiple times! You simply run it once and store the result for later invocations, saving time at the cost of some memory. Of course, the advantage is bigger if the computation takes some time.

You already learned how to implement memoization with Kotlin using the `lazy` function. It would be a good exercise to implement memoization for any function of type `Fun<A, B>`. How would you implement it?

Note: You can try to solve this problem on your own as a fun exercise before looking at the proposed solution. :]

Open the initially empty Memoization.kt file and write the following code:

``````fun <A, B> Fun<A, B>.memo(): Fun<A, B> { // 1
val cache by lazy { mutableMapOf<A, B>() } // 2
return { a: A ->  // 3
val cached = cache[a] // 4
if (cached == null) {
cache[a] = this(a)
}
cache[a]!! // 5
}
}
``````

In this code, you:

1. Define `memo` as an extension function for `Fun<A, B>`. The return type is still `Fun<A, B>`. Remember `Fun<A, B>` is an alias of the type `(A) -> B`.
2. Use `lazy` to define `MutableMap<A, B>`, which will store the values to cache. In this case, `lazy` allows you to create just one instance of the cache in a lazy way.
3. Return a lambda accepting a parameter of type `A`. This is a lambda of type `Fun<A, B>`.
4. Check in the cache to see if you already have a result for the given input `a`. If not, you invoke the function and store the result.
5. Now you have the result, cached or not, to return.

To test this function, write this simple code:

``````fun main() {
val testFunction = { a: Int -> println("Evaluating... \$a"); a * 2 } // 1
println("Running testFunction 4 times")
testFunction(2) // 2
testFunction(2)
testFunction(2)
testFunction(3)
val memoTestingFunction = testFunction.memo() // 3
println("Running memoTestingFunction 4 times")
memoTestingFunction(2) // 4
memoTestingFunction(2)
memoTestingFunction(2)
memoTestingFunction(3)
}
``````

In this code, you:

1. Define a simple `testFunction` that returns double the input `Int`, printing a message to give evidence of the actual invocation.
2. Invoke `testFunction` four times. The first three times, you use the input `2`, passing `3` instead in the last invocation.
3. Use `memo` to get the memoized version of `testFunction` you save in `memoTestingFunction`.
4. Invoke `memoTestingFunction` four times using the same parameters you used earlier for `testFunction`.

Run the code, and you get:

``````Running testFunction 4 times
Evaluating... 2
Evaluating... 2
Evaluating... 2
Evaluating... 3
Running memoTestingFunction 4 times
Evaluating... 2
Evaluating... 3
``````

As you see, you have an output message every time you invoke `testFunction`. When you invoke `memoTestingFunction`, you have a message only the first time you pass a specific input value. This is exactly what you expect from `memo`.

## Create a lazy stream with Kotlin

You learned that a lambda expression allows you to run some code — or evaluate some expression — later. This makes lambda expressions perfect for generating some sequences of values. Suppose you want to create a function returning the first `N` even numbers. A first, eager solution is the following. Add this to Stream.kt:

``````fun eagerEvenSequence(n: Int): List<Int> = List(n) { i -> i * 2 }
``````

In this simple function, you create a `List<Int>` using the constructor `List` provides. It requires the `size` of the `List` and a lambda expression invoked for each element, which returns the value given its index. So far, so good. This solution has some problems, though:

1. The `eagerEvenSequence` function returns a `List` with all the values you might need. Here, the “might” is important because you might not need all of them.
2. If you just need the last value, you have to get the complete `List` first anyway.
3. If you need more values, you must invoke `eagerEvenSequence` with a new input value.

You can see all this by running the following code:

``````fun main() {
println(eagerEvenSequence(5))
}
``````

The output is:

``````[0, 2, 4, 6, 8]
``````

In this case, the example is very simple, but in other cases, it might be useful to get a value of the sequence only if you really need it and when you really need it.

Next, add the following code to the same Stream.kt file:

``````fun evenPositiveStream(): () -> Int { // 1
var count = -2 // 2
return { count += 2; count } // 3
}
``````

In this code, you:

1. Define `evenPositiveStream` as a function returning another function of type `() -> Int`, which provides an even `Int` value every time you invoke it.
2. Initialize `count` to `-2`. This weird initial value allows you to make the following line shorter and still return `0` as the first value after you add `2`.
3. You return a lambda expression that adds `2` to `count` and returns the new value.

You can test the previous code by adding this to the same file:

``````fun main() {
val evenSequence = evenPositiveStream() // 1
5.times { // 2
println(evenSequence())
}
}
``````

In `main`, you:

1. Create `evenSequence`, invoking `evenPositiveStream`.
2. Use the `times` utility function you find in Utils.kt to invoke `evenSequence` five times.

The output you get is:

``````0
2
4
6
8
``````

More importantly:

1. You can persist the values of the sequence only if you really need them.
2. If you need more values, just invoke `evenSequence` more times.

Note: You might argue that in the case of `eagerEvenSequence`, you could just return double the input parameter. This is true, but, as the next exercise proves, you’re not always so lucky. :]

This is a very simple example of how lazy evaluation with lambda expressions allows you to create sequences in an optimal way.

Exercise 4.6: Can you create a function `fibo` returning the values of a Fibonacci sequence? Remember, every value in a Fibonacci sequence is the sum of the previous two elements. The first two elements are `0` and `1`. The first values are, then:

``````0  1  1  2  3  5  8  13  21 ...
``````

Try to answer without the support of IntelliJ, and check your solutions in Appendix D or the challenge project.

## Normal-order evaluation

Note: The following two sections are optional. They give you some information about the normal-order evaluation used by languages like Haskell, in case you’re curious to know more. If you’re not curious, you can skip right to the challenges.

At the beginning of the chapter, you learned that Kotlin evaluates all expressions using applicative-order evaluation. This means it evaluates the expressions you pass as input parameters of a function before the function itself. After that, you also learned that Kotlin allows you to implement lazy evaluation using lambda expressions. Some other languages, like Haskell, use normal-order evaluation instead. But what does that mean, and is it possible to simulate normal-order evaluation with Kotlin?

Normal-order evaluation always reduces the leftmost, outermost reducible function expression. This means you evaluate the function before the expression you pass as a parameter to the same function. Kotlin doesn’t have applicative-order evaluation like Haskell, but with lazy evaluation, you can achieve something similar. Suppose you want to reduce the same function you saw at the beginning of the chapter:

``````3 * avg(x, y)
``````

You want to evaluate the function before the expression you pass as a parameter. Open NormalOrder.kt and add the following:

``````fun addL(x: () -> Int, y: () -> Int): () -> Int {
return { println("addL"); x() + y() }
}
``````

`addL` has some interesting things to note:

• The input parameters are not executed expressions but lazily executable lambda expressions.
• You don’t evaluate the expression you use as the input parameter before the evaluation of `addL` but as part of it.
• You use `println` to have evidence of `addL`.
• The function returns a lambda expression.

You can now apply the same logic to the following functions. Add these to the same NormalOrder.kt file:

``````fun tripleL(x: () -> Int): () -> Int {
}

fun divideL(x: () -> Int, y: () -> Int): () -> Int {
return { println("divideL"); x() / y() }
}

fun averageL(x: () -> Int, y: () -> Int): () -> Int {
return { println("averageL"); divideL(addL(x, y), { 2 })() }
}
``````

For testing its behavior, add the following `main`:

``````fun main() {
tripleL(averageL({ 2 }, { 4 }))()
}
``````

When you run the previous code, you get:

``````tripleL
averageL
divideL
averageL
divideL
averageL
divideL
``````

Try to mimic this by applying the substitution model. In this case, you have a longer sequence than you did earlier in this chapter because you evaluate the external function on the left first.

``````tripleL(averageL({2},{4}))()
{{averageL({2},{4})()+averageL({2},{4})()}()+averageL({2},{4})()}()
{{(2+4)/2}()+averageL({2},{4})()}()+averageL({2},{4})()}()
{{(2+4)/2}()+{(2+4)/2}()+averageL({2},{4})()}()
{{(2+4)/2}()+{(2+4)/2}()+{(2+4)/2}()}()
{3+3+3}()
{9}()
``````

As you can see, the leftmost function is the one you’re evaluating in each step.

### Applicative-order vs. normal-order evaluations

Looking at the previous examples and considering how Kotlin works, you understand how lazy evaluation is a balanced compromise between applicative-order and normal-order evaluation strategies. It allows you to control where to define your expression and when to evaluate it. If you use the Kotlin `lazy` function, you also get the benefit of memoization, which is very good in the case of expensive — and pure — functions.

In particular, using the Kotlin lazy function, you get three different synchronization modes for free through the `LazyThreadSafetyMode` enum class. With this, you can decide how a lazy instance synchronizes initialization among multiple threads. Possible values are:

• SYNCHRONIZED: The initialization is safe because only a single thread at a time can access the lambda expression you pass as a parameter. This is the default mode.
• PUBLICATION: The lambda expression you pass as a parameter can be evaluated several times on concurrent access to an uninitialized lazy instance value. However, only the first returned value will be used as the actual value.
• NONE: The lambda expression can be evaluated multiple times from different threads, and its behavior is undefined.

In the last example, you might have the impression that normal-order evaluates the same expressions multiple times, which is a problem that lazy evaluation solves elegantly. On the other hand, applicative-order evaluation doesn’t always work well with recursion. If the function you pass as a parameter is recursive, it might not end. Or the expression could never return, like in this example you can write in EvalExamples.kt:

``````fun neverEnding(): Int { // 1
while (true){}
}

fun double(x: Int): Int = x + x // 2

fun main() {
double(neverEnding()) // 3
}
``````

In this code, you:

1. Define `neverEnding` using an infinite loop as a function that never returns.
2. Create `double` as a simple function returning the double of its input parameter.
3. Define `main`, which simply uses `neverEnding` invocation as an input parameter of `double`.

Run this code, and the program will never complete.

## Challenges

In this chapter, you learned many important concepts about expression evaluation, lambda functions and lazy evaluation. You’ve already done some interesting exercises, but here you have some additional challenges. Have fun! :]

### Challenge 1: Handling nullability

In Exercise 4.5, you created `myLazy`, which allowed you to implement memoization for a generic lambda expression of type `() -> A`. Can you now create `myNullableLazy`, supporting optional types with the following signature?

``````fun <A> myNullableLazy(fn: () -> A?): () -> A? // ...
``````

### Challenge 2: Functions and set again

You might be aware of Euler’s number e. It’s a mathematical constant of huge importance that you can calculate in very different ways. It’s an irrational number like pi that can’t be represented in the form `n/m`. Here, you’re not required to know what it is, but you can use the following formula:

Can you create a sequence that provides the sum of the `n` terms of the given formula?

## Key points

• You define evaluation strategy as the relationship between the point in your code where you define your expression and the point when the expression is actually evaluated.
• With applicative-order evaluation, a function is executed only when all the expressions you pass as input parameters are evaluated, starting from the leftmost parameter.
• A lambda expression is an anonymous function you can use as a value.
• Type inference is the mechanism a compiler uses to understand the element types involved in an expression.
• The type of lambda expression is a function type.
• A lambda expression is contravariant for the input type and covariant for the output type.
• Memoization is the process that allows you to save the result of a function in memory to reuse it more efficiently.
• Pure functions can always be memoized.
• Pure evaluation allows you to easily implement infinite sequences of values in a very efficient way.

## Where to go from here?

Congratulations! You’ve completed another challenging chapter about expression evaluation and lambda functions. You had the chance to solve some fun exercises, and you’ve already started implementing some higher-order functions — which is the topic of the next chapter. See you there. :]

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.