23

  def fibSeq(n: Int): List[Int] = {
    var ret = scala.collection.mutable.ListBuffer[Int](1, 2)
    while (ret(ret.length - 1) < n) {
      val temp = ret(ret.length - 1) + ret(ret.length - 2)
      if (temp >= n) {
        return ret.toList
      }
      ret += temp
    }
    ret.toList
  }

So the above is my code to generate a Fibonacci sequence using Scala to a value n. I am wondering if there is a more elegant way to do this in Scala?

2
  • You should probably ask this on programmers.se. as it is, this question is too broad to be answered reasonably. There are lots of ways to define fibonacci sequences, and each has their owns strenghts and weaknesses.
    – Polygnome
    Mar 19, 2016 at 16:50
  • Similar question: stackoverflow.com/questions/7388416/…
    – kxmh42
    Sep 11, 2016 at 14:30

7 Answers 7

93

This is a bit more elegant:

val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_ + _)

With Streams you "take" a number of values, which you can then turn into a List:

scala> fibs take 10 toList
res42: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

Update: I've written a blog post which goes more detail regarding how this solution works, and why you end up with a Fibonacci sequence!

9
  • 1
    Ooh, I didn't know about scanLeft, that's really cool. Mar 26, 2012 at 6:08
  • 7
    @LuigiPlinge Isn't this a forward reference? Only works if I apply the lazy keyword. Apr 2, 2013 at 3:09
  • 10
    @HunterMcMillen actually it depends where you're defining it. If in the top level of an object or in the REPL, you don't. If it's within a method then you do need the lazy. Apr 2, 2013 at 4:57
  • 5
    @DCKing It's due to scope. A member of an class can refer to any other member, and it doesn't matter what order they're defined in. But in a method, you can only refer to things that have been defined above. Apr 18, 2014 at 13:50
  • 2
    @LuigiPlinge I understand your point but I want to learn immutable style programming in scala using this fibonacci sequence.
    – Dinesh
    Sep 10, 2014 at 13:59
31

There are many ways to define the Fibonacci sequence, but my favorite is this one:

val fibs:Stream[Int] = 0 #:: 1 #:: (fibs zip fibs.tail).map{ t => t._1 + t._2 }

This creates a stream that is evaluated lazily when you want a specific Fibonacci number.

EDIT: First, as Luigi Plinge pointed out, the "lazy" at the beginning was unnecessary. Second, go look at his answer, he pretty much did the same thing only more elegantly.

8
  • Is it possible with for-comprehension construct?
    – nobody
    Mar 25, 2012 at 22:24
  • 2
    Doesn't need to be a lazy val; being lazy just means that's it doesn't eagerly evaluate the first term 0, which you already given as a literal Mar 26, 2012 at 3:41
  • It seems like there should be a better way to do (foo zip bar).map{ t => f(t._1, t._2) }. In Haskell it would be zipWith f foo bar, and in Racket, (map f foo bar)
    – Dan Burton
    Mar 26, 2012 at 3:48
  • @DanBurton: In Scala you can write (foo zip bar) map f if f expects a tuple and (foo zip bar) map f.tupled if f expects two parameters.
    – kiritsuku
    Mar 26, 2012 at 14:12
  • Contrary to my previous comment, this does need to be a lazy val if it's defined as a local variable rather than an an object/class field. Because when it's a field the compiler translates fibs to this.fibs, so you can get away without the lazy. Meh. Probably best to keep it in for consistency. Apr 16, 2012 at 17:55
7

Not as elegant as Streams, not lazy, but tailrecursive and handles BigInt (which is easy to do with Luigis scanLeft too, but not so with Tal's zip - maybe just for me).

@tailrec 
def fib (cnt: Int, low: BigInt=0, high: BigInt=1, sofar: List[BigInt]=Nil): List[BigInt] = {
  if (cnt == 0) (low :: sofar).reverse else fib (cnt - 1, high, low + high, low :: sofar) }

scala> fib (75)
res135: List[BigInt] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050)

2
  • 2
    Similar: def fib(n: Int, s: List[BigInt] = List(1, 0)): List[BigInt] = if (n <= 2) s.reverse else fib(n - 1, s(0) + s(1) :: s) Mar 26, 2012 at 12:06
  • 1
    BTW to convert Tal's version to handle BigInt, all you have to do is change [Int] on the left hand side to [BigInt]! The Int literals on the right are implicitly converted. Mar 29, 2012 at 3:57
7

My favorite version is:

def fibs(a: Int = 0, b: Int = 1): Stream[Int] = Stream.cons(a, fibs(b, a+b))

With the default values you can just call fibs() and get the infinite Stream.

I also think it's highly readable despite being a one liner.

If you just want the first n then you can use take like fibs() take n, and if you need it as a list fibs() take n toList.

2

Here's yet another approach again using *Stream*s on an intermediary tuples:

scala> val fibs = Stream.iterate( (0,1) ) { case (a,b)=>(b,a+b)  }.map(_._1) 
fibs: scala.collection.immutable.Stream[Int] = Stream(0, ?)

scala> fibs take 10 toList
res68: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)
0

I find this implementation to be more legible:

def fibonacci: Stream[Int] = {
    def loop(a: Int, b: Int): Stream[Int] = (a + b) #:: loop(b, b + a)
    loop(0, 1)
}
0
def fib:Stream[Int] ={
  def go(f0: Int, f1:Int): Stream[Int] = {
    Stream.cons(f0,go(f1,f0+f1))
  }
  go(0,1)
}

Not the answer you're looking for? Browse other questions tagged or ask your own question.