How to define a infinite Lazy List using a given function or property in Scala?

user_16092224 0
Viewed 146

I recently was seeing an advanced Scala course in Rock the JVM and, in one lesson, Daniel purposed to create a set using propertys (functions going from A to Boolean), the implementation of this Set can be found here.

For example, he was able to create a set "containing" all the naturals by doing this:

val naturals = PBSet[Int](_ => true)

Then he could verify if an input was contained inside that set by doing naturals.contains(input).

My question is, is there any way to accomplish this using Lazy Lists or even better, Lazy Vectors or Lazy Maps?

For instance, given a fibonacci(n) function that returns the nth Fibonacci number, a lazy list containing all the posible outputs for that function would look like something like this:

val allFibonacciNumbers: LazyList[Long] = LazyList.generate(n => fibonacci(n))

I know something similiar could be done by doing this:

val allFibonacciNumbersV2: LazyList[Long] = LazyList.iterate(0L)(n => n + 1).map(n => fibonacci(n))

The problem of that implementation is the start value of the iterate function: It is not going to give all the possible outputs of any function, just the ones after that.

So, how could such a task be accomplished using a combination of the Porperty based Set and the Lazy List? Or even better, with a Lazy Vector or Lazy Map?

I couldn't find anything similar, the closest I could find was something called property based test but that's about it.

Thank you for the immense help and for reading my question. Have a great day!

computed-properties lazy-sequences lazy-evaluation scala functional-programming
1 Answers

Well, there is no "LazyMap" out of the box, but it is rather trivial to just roll your own.

Your comments sound like you already know how to compute Fibonacci with a LazyList, from there, you just need to memoize the result:

object FF { 
   val fm = mutable.Map.empty[Int, BigInt] 
   val fib: LazyList[BigInt] = BigInt(0) #:: BigInt(1) #:: 
       fib.zip(fib.tail).map(p => p._1 + p._2)
   def apply(n: Int) = fm.getOrElseUpdate(n, fib(n))
}

Now, things like FF(100) are linear the first time, and constant time after that. If you do FF(100), and then FF(99), that second call is still linear for the first time though. Technically, it could be optimized to be constant time too, because fib(99) is already available, but I don't think it's worth the trouble ... and extra storage.

user_42545170
Related