CODEWITHSUNDEEP
listscalacollectionsfilterlazy-evaluation
FaY
FaY

Reputation: 103

Lazy evaluation steps : filtering a list

I have some questions regarding lazy evaluation in Scala. This is the sample code:

val people=List(("Mark", 32), ("Bob", 22), ("Jane", 8), 
         ("Jill", 21), ("nick", 50), ("Nancy", 42), 
         ("Mike", 19), ("Sara", 12), ("Paula", 42), 
         ("John", 21))

def isOlderThan17(person: (String,Int)) = {
  println(s"isOlderThan 17 called for $person")
  val(_,age) = person
  age > 17
}

def nameStartsWithJ(person: (String, Int)) = {
  println(s"isNameStartsWithJ called for $person")
  val (name,_) = person
  name.startsWith("J")
}

println(people.view.filter(p => isOlderThan17(p))
                   .filter(p => nameStartsWithJ(p))
                   .last)

Output :

isOlderThan 17 called for (Mark,32)
isNameStartsWithJ called for (Mark,32)
isOlderThan 17 called for (Bob,22)
isNameStartsWithJ called for (Bob,22)
isOlderThan 17 called for (Jane,8)
isOlderThan 17 called for (Jill,21)
isNameStartsWithJ called for (Jill,21)
isOlderThan 17 called for (Mark,32)      //Here is the problem.
isNameStartsWithJ called for (Mark,32)
isOlderThan 17 called for (Bob,22)
isNameStartsWithJ called for (Bob,22)
isOlderThan 17 called for (Jane,8)
isOlderThan 17 called for (Jill,21)
isNameStartsWithJ called for (Jill,21)
isOlderThan 17 called for (nick,50)
isNameStartsWithJ called for (nick,50)
isOlderThan 17 called for (Nancy,42)
isNameStartsWithJ called for (Nancy,42)
isOlderThan 17 called for (Mike,19)
isNameStartsWithJ called for (Mike,19)
isOlderThan 17 called for (Sara,12)
isOlderThan 17 called for (Paula,42)
isNameStartsWithJ called for (Paula,42)
isOlderThan 17 called for (John,21)
isNameStartsWithJ called for (John,21)
(John,21)

Why did the evaluation have to be restarted (back again from "Mark") after "Jill" had been found? Why didn't it continue the evaluation until the end of the list?

Upvotes: 2

Views: 1448

Answers (2)

0x6C38
0x6C38

Reputation: 7076

Why did the evaluation have to be restarted (back again from "Mark") after "Jill" had been found?

Because each filter results in a new collection that contains only the filtered items. Use a stream to avoid this:

println(people.toStream
              .filter(p => isOlderThan17(p))
              .filter(p => nameStartsWithJ(p))
              .last)

From Stream vs Views vs Iterators

Stream is a lazy list indeed. In fact, in Scala, a Stream is a List whose tail is a lazy val. Once computed, a value stays computed and is reused. Or, as you say, the values are cached.

In this case you're only composing filters so you might as well just combine the two predicates and do the filtering only once:

println(people.filter(p => isOlderThan17(p) && nameStartsWithJ(p))
              .last)

Upvotes: 1

Victor Moroz
Victor Moroz

Reputation: 9225

It seems to be related to the implementation of last in view. If you do it this way it won't restart:

people.view
      .filter(isOlderThan17(_))
      .filter(nameStartsWithJ(_))
      .fold(None)((x, y) => Some(y))

Looks like last is trying to access head twice, which in your case means you need to find the first element of people.view.filter(isOlderThan17(_)) twice and so view has to recompute it two times.

UPDATE

Here's the definition of last in TraversableLike:

def last: A = {
    var lst = head
    for (x <- this)
      lst = x
    lst
  }

The first element is indeed accessed twice.

Upvotes: 3

Related Questions