The easiest way to write {1, 2, 4, 8, 16 } in Scala

Question

I was advertising Scala to a friend (who uses Java most of the time) and he asked me a challenge: what's the way to write an array {1, 2, 4, 8, 16} in Scala.

I don't know functional programming that well, but I really like Scala. However, this is a iterative array formed by (n*(n-1)), but how to keep track of the previous step? Is there a way to do it easily in Scala or do I have to write more than one line of code to achieve this?

Answer 1

Array.iterate(1, 5)(2 * _)

or

Array.iterate(1, 5)(n => 2 * n)

---

Elaborating on this as asked for in comment. Don't know what you want me to elaborate on, hope you will find what you need.

This is the function iterate(start,len)(f) on object Array (scaladoc). That would be a static in java.

The point is to fill an array of len elements, from first value start and always computing the next element by passing the previous one to function f.

A basic implementation would be

import scala.reflect.ClassTag

def iterate[A: ClassTag](start: A, len: Int)(f: A => A): Array[A] = {
  val result = new Array[A](len)
  if (len > 0) {
    var current = start
    result(0) = current
    for (i <- 1 until len) {
      current = f(current)
      result(i) = current
    }
  }
  result
}

(the actual implementation, not much different can be found here. It is a little different mostly because the same code is used for different data structures, e.g List.iterate)

Beside that, the implementation is very straightforward . The syntax may need some explanations :

def iterate[A](...) : Array[A] makes it a generic methods, usable for any type A. That would be public <A> A[] iterate(...) in java.

ClassTag is just a technicality, in scala as in java, you normally cannot create an array of a generic type (java new E[]), and the : ClassTag asks the compiler to add some magic which is very similar to adding at method declaration, and passing at call site, a class<A> clazz parameter in java, which can then be used to create the array by reflection. If you do e.g List.iterate rather than Array.iterate, it is not needed.

Maybe more surprising, the two parameters lists, one with start and len, and then in a separate parentheses, the one with f. Scala allows a method to have severals parameters lists. Here the reason is the peculiar way scala does type inference : Looking at the first parameter list, it will determine what is A, based on the type of start. Only afterwards, it will look at the second list, and then it knows what type A is. Otherwise, it would need to be told, so if there had been only one parameter list, def iterate[A: ClassTag](start: A, len: Int, f: A => A), then the call should be either

• Array.iterate(1, 5, n : Int => 2 * n)
• Array.iterate[Int](1, 5, n => 2 * n)
• Array.iterate(1, 5, 2 * (_: int))
• Array.iterate[Int](1, 5, 2 * _)

making Int explicit one way or another. So it is common in scala to put function arguments in a separate argument list. The type might be much longer to write than just 'Int'.

A => A is just syntactic sugar for type Function1[A,A]. Obviously a functional language has functions as (first class) values, and a typed functional language has types for functions.

In the call, iterate(1, 5)(n => 2 * n), n => 2 * n is the value of the function. A more complete declaration would be {n: Int => 2 * n}, but one may dispense with Int for the reason stated above. Scala syntax is rather flexible, one may also dispense with either the parentheses or the brackets. So it could be iterate(1, 5){n => 2 * n}. The curlies allow a full block with several instruction, not needed here.

As for immutability, Array is basically mutable, there is no way to put a value in an array except to change the array at some point. My implementation (and the one in the library) also use a mutable var (current) and a side-effecting for, which is not strictly necessary, a (tail-)recursive implementation would be only a little longer to write, and just as efficient. But a mutable local does not hurt much, and we are already dealing with a mutable array anyway.

Answer 2

always more than one way to do it in Scala:

scala> (0 until 5).map(1<<_).toArray
res48: Array[Int] = Array(1, 2, 4, 8, 16)

or

scala> (for (i <- 0 to 4) yield 1<<i).toArray
res49: Array[Int] = Array(1, 2, 4, 8, 16)

or even

scala> List.fill(4)(1).scanLeft(1)(2*_+0*_).toArray
res61: Array[Int] = Array(1, 2, 4, 8, 16)

Answer 3

The other answers are fine if you happen to know in advance how many entries will be in the resulting list. But if you want to take all of the entries up to some limit, you should create an Iterator, use takeWhile to get the prefix you want, and create an array from that, like so:

scala> Iterator.iterate(1)(2*_).takeWhile(_<=16).toArray
res21: Array[Int] = Array(1, 2, 4, 8, 16)

It all boils down to whether what you really want is more correctly stated as

• the first 5 powers of 2 starting at 1, or
• the powers of 2 from 1 to 16

For non-trivial functions you almost always want to specify the end condition and let the program figure out how many entries there are. Of course your example was simple, and in fact the real easiest way to create that simple array is just to write it out literally:

scala> Array(1,2,4,8,16)
res22: Array[Int] = Array(1, 2, 4, 8, 16)

But presumably you were asking for a general technique you could use for arbitrarily complex problems. For that, Iterator and takeWhile are generally the tools you need.