CODEWITHSUNDEEP
scala
Vololodymyr
Vololodymyr

Reputation: 2288

Generate sequence with unknown bound, based on condition

I want to generate sequance of all fibonacci numbers, that less then 10000

For example, this will generate 40 fibonacci numbers. But i want to stop generate them with some condition. How can i do this?

  def main(args: Array[String]) {
    val fibonacciSequence = for(i <- 1 to 40) yield fibonacci(i) 
    println(fibonacciSequence)
  }

  def fibonacci(i: Int) : Int = i match {
    case 0 => 0
    case 1 => 1
    case _ => fibonacci(i - 1) + fibonacci(i - 2);
  }

I want something like this: for(i <- 1 to ?; stop if fibonacci(i) > 100000)

Upvotes: 0

Views: 69

Answers (2)

Odomontois
Odomontois

Reputation: 16308

This method, involving lazy infinite collection calculation, could produce suitable result:

import scala.Numeric.Implicits._

def fibonacci[N: Numeric](a: N, b: N): Stream[N] = a #:: fibonacci(b, a + b)

so 

fibonacci(0L,1L).takeWhile(_ < 1000L).toList

yields 

List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987)

If you don't want to use intermediate value to cache collection of proper type and init, you could just declare a val like this:

val fib: Stream[Long] = 0 #:: 1 #:: (fib zip fib.tail map { case (a, b) => a + b })

Upvotes: 3

elm
elm

Reputation: 20415

Using iterators and memoization (computing the current result based in the latest ones, not recomputing what has already been done), (method from Rosetta, similar to Odomontois's streams),

def fib() = Iterator.iterate((0,1)){ case (a,b) => (b,a+b)}.map(_._1)

To get the first nth values consider for instance,

def nfib(n: Int) = fib().zipWithIndex.takeWhile(_._2 < n).map(_._1).toArray

To get consecutive values up to a given condition or predicate, 

def pfib(p: Int => Boolean) = fib().takeWhile(p).toArray

Thus, for example

nfib(10)
Array(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

pfib( _ < 55)
Array(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

Upvotes: 1

Related Questions