CODEWITHSUNDEEP
scalarecursionfunctional-programming
David Frank
David Frank

Reputation: 6092

How to generate a list in Scala, where each item depends on the preceding item

Say, I have a recursive rule:

f(0) = 2
f(n) = f(n-1) * 3 - 2

I need to generate a list for n ∈ [0, 10].

If I was interested in f(10), I could use foldLeft like this:

(1 to 10).foldLeft(2)((z, _) => z * 3 - 2)

I want to achieve the following in a concise and functional style:

val list = new ListBuffer[Int]
list += 2
(1 to 10).foreach {
    list += list.last * 3 - 2
}

What's the solution?

Upvotes: 1

Views: 87

Answers (2)

elm
elm

Reputation: 20415

One of the multiple approaches involves for instance the use of scanLeft as follows,

(1 to 10).scanLeft(2)( (acc,_) => acc*3-2)

This applies the function onto the latest (accumulated) result.

Update

Also consider this Iterator

val f = Iterator.iterate(2)(_*3-2)

and so

(1 to 10).map(_ => f.next)

For a large number of iterations, initial value 2: Int may be cast onto BigInt(2) so as to avoid overflow for instance in 

(1 to 100).map(_ => f.next)

Upvotes: 3

Noah
Noah

Reputation: 13959

You can use a Stream to generate this list lazily and functionally:

  val stream: Stream[Int] = {
    def next(i: Int): Stream[Int] = {
      val n = i * 3 - 2
      n #:: next(n)
    }
    2 #:: next(2)
  }

  println(stream.take(11).toList)
  //prints List(2, 4, 10, 28, 82, 244, 730, 2188, 6562, 19684, 59050)

Upvotes: 4

Related Questions