Last updated on

Find, with lazy evaluation

Points
10 pts
Topics
Laziness
Files to submit
src/main/scala/find/find.scala

Introduction

Recall that in the first callback lab we were not able to refactor the findFirstByNameAndPrint function, even though it is quite similar to the other ones. But today, using lazy evaluation we will be able to generalize it as well.

Step 1: Implement findLazy

Implement the findLazy function in find.scala.

This function takes two arguments:

  1. a root cs214.Entry to search in,
  2. a predicate function that takes an cs214.Entry and returns a Boolean.

It should return a LazyList[Entry] containing all the entries satisfying the predicate.

Be careful, until a particular result is requested, this function should not do any useless evaluation. For instance, given the following code, which prints all entry lazily, nothing gets printed immediately:

// Nothing is printed there
val entries = findLazy(entry, e => {println(e.name()); true})

But if we take the first element, then it will evaluate the head of the list, and hence, prints its name:

// This prints the first element's name
entries(0)

// This prints the second element's name
entries(1)

Also, this function should iterate through the tree lazily. Even if the tree happens to be infinite, it would still work.

Step 2: Rewrite the findFirstByNameAndPrint function

Rewrite findFirstByNameAndPrint using the findLazy function you just implemented.

Step 3: Rewrite the findAndPrint function

Notice how the findLazy function is more versatile than the initial findAndPrint. What’s interesting is that we have now split the control part (how much should we iterate) from the iteration through the file tree itself. This can be used to implement all sort of control flow, such as taking only the first element, like you did in Step 2, or taking all elements, which is what findAndPrint is doing. Therefore, you should now update findAndPrint using findLazy. This will allow you to use the existing test suite to verify if your implementation maintains its previous behavior.

Testing

This lab includes all the previous tests, plus a new suite in FindLazyTest.scala, it can be relevant to have a look, if you are unsure about how lazy your implementation should be.

You can run all suites as usual with:

$ sbt test

The tests in FindLazyTest.scala and FindTest.scala will be marked.

© 2023, 2024 EPFL. All rights reserved.