CODEWITHSUNDEEP
scalafunctional-programmingscala-collections
thesamet
thesamet

Reputation: 6582

Build a vector recursively

I have a function f(a: A): A and an integer N. I'd like to write a function that will return the following Vector[A]:

Vector(a, f(a), f(f(a)), f(f(f(a))), ..., f^{N}(a))

where f^{N} denotes applying f recursively N times. N may be relatively large. I am looking for a solution that will not require reversing a data structure or traversing it more than once. Clearly, there are many ways to do this; I am looking for functional, idiomatic and readable code.

Upvotes: 0

Views: 329

Answers (2)

Eastsun
Eastsun

Reputation: 18859

{Vector, List, Array, ...}.iterator

def iterate[A](start: A, len: Int)(f: (A) ⇒ A): Vector[A]

Produces a collection containing repeated applications of a function to a start value. start the start value of the collection len the number of elements contained inthe collection f the function that's repeatedly applied returns a collection with len values in the sequence start, f(start), f(f(start)), ...

scala> def f(x: Int): Int = if(x%2 == 0) x/2 else 3*x+1
f: (x: Int)Int

scala> Vector.iterate(10000, 10)(f)
res0: scala.collection.immutable.Vector[Int] = 
 Vector(10000, 5000, 2500, 1250, 625, 1876, 938, 469, 1408, 704)

Or if you really want to implement it yourself, here is a possible solution

scala> def iterator[A](start: A, len: Int)(f: A => A): Vector[A] = len match {
     |   case 0 => Vector()
     |   case _ => start +: iterator(f(start), len-1)(f)
     | }
iterator: [A](start: A, len: Int)(f: A => A)Vector[A]

scala> iterator(10000, 100)(f)
res1: Vector[Int] = Vector(10000, 5000, 2500, 1250, 625, 1876, 938, 469, 1408, 
704, 352, 176, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 
1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 
1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 
1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4)

Upvotes: 5

thesamet
thesamet

Reputation: 6582

(1 to N).foldLeft(Vector(a)) { (acc, a) => acc :+ f(acc.last) }

Upvotes: 1

Related Questions