Scala views -- non-strict vs. lazy

Question

I am trying to create a "lazy" map of objects (actually, they are actors, but I am asking my question with a more trivial example).

Scala views are, in a sense, lazy. But their laziness is really just non-strictness. That's to say, the values are effectively call-by-name, which is in turn to say that the values are evaluated, when required, by invoking a Function0 (a no-parameter function).

What I'm interested in is a collection that is evaluated lazily, but is evaluated only once. Here's the kind of thing I'm looking for:

val x = Map(1->2, 2->2).view
val y = x map {case (k,v) => (k,{println("Hello");v.toString})}
val z1 = y.find{case (k,_) => k==1}
val z2 = y.find{case (k,_) => k==1}

When I put this into a Scala worksheet, what I get is:

x: scala.collection.IterableView[(Int, Int),scala.collection.immutable.Map[Int,Int]] = IterableView(...)
y: scala.collection.IterableView[(Int, String),Iterable[_]] = IterableViewM(...)
Hello
z1: Option[(Int, String)] = Some((1,1))
Hello
z2: Option[(Int, String)] = Some((1,1))

Everything is just as it should be. Except that I don't want to see that second "Hello". In other words, I only want the mapped function (toString) to be invoked once -- when needed.

Does anyone have a suggestion of how to achieve my goal? It's not super-important but I'm curious if it can be done.

Answer 1

You can almost get what you want using a Stream:

scala> val x = TreeMap(1->2, 2->2) // to preserve order
x: scala.collection.immutable.TreeMap[Int,Int] = Map(1 -> 2, 2 -> 2)

scala> val y = x.toStream map {case (k,v) => (k,{println(s"Hello $k");v.toString})}
Hello 1
y: scala.collection.immutable.Stream[(Int, String)] = Stream((1,2), ?)

scala> y.find{case (k,_) => k==1}
res8: Option[(Int, String)] = Some((1,2))

scala> y.find{case (k,_) => k==2}
Hello 2
res9: Option[(Int, String)] = Some((2,2))

as you can see, the first element is evaluated strictly, but the others are evaluated and memoized on-demand

If you make the stream itself a lazy val, you get what you want:

scala>   val x = TreeMap(1->2, 2->2) // to preserve order
x: scala.collection.immutable.TreeMap[Int,Int] = Map(1 -> 2, 2 -> 2)

scala>   lazy val y = x.toStream map {case (k,v) => (k,{println(s"Hello $k");v.toString})}
y: scala.collection.immutable.Stream[(Int, String)] = <lazy>

scala>   y.find{case (k,_) => k==1}
Hello 1
res10: Option[(Int, String)] = Some((1,2))

scala>   y.find{case (k,_) => k==1}
res11: Option[(Int, String)] = Some((1,2))

If you don't mind evaluating the whole collection at once when you use it, you just need a lazy val and the collection can stay what it is (map, list etc)

val x = TreeMap(1->2, 2->2) 
lazy val y = x map {case (k,v) => (k,{println(s"Hello $k");v.toString})}

I don't think you can have a (really) lazy map, but I'd be happy if someone proved me wrong :)

---

edit: You can have a (sort of) lazy map by wrapping your values like this:

class Lazy[T](x: => T) {
  lazy val value = x
  override def toString = value.toString
}

object Lazy {
  implicit def toStrict[T](l: Lazy[T]): T = l.value
}

val x = TreeMap(1->2, 2->2)
lazy val y = x map {case (k,v) => (k, new Lazy({println(s"Hello $k");v.toString}))}

y.find{case (k,v) => v.indexOf("x");k==1} // let's use v to evaluate it, otherwise nothing gets printed
y.find{case (k,v) => v.indexOf("x");k==1}

The implicit conversion allows you to use your values as if they were of their original type

Answer 2

I would propose alternative solution, instead of laziness. What if your v will be function but not value. In such case you'd be able to control execution whenever you need without relying on collections laziness...

val y = x map {case (k,v) => (k,() => {println("Hello");v.toString})}

Answer 3

I do not know of any collection API that offers that kind of laziness. However, I think you can achieve what you want with function memoization as described here:

case class Memo[I <% K, K, O](f: I => O) extends (I => O) {
  import collection.mutable.{Map => Dict}
  val cache = Dict.empty[K, O]
  override def apply(x: I) = cache getOrElseUpdate (x, f(x))
}

val x = Map(1->2, 2->2).view
val memo = Memo { v: Int =>
  println("Hello")
  v.toString
}
val y = x.map { case (k, v) =>
  (k, memo(v))
}
val z1 = y.find{case (k,_) => k==1}
val z2 = y.find{case (k,_) => k==1}

output:

Hello
z1: Option[(Int, String)] = Some((1,2))
z2: Option[(Int, String)] = Some((1,2))