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?

nobody
  • 2,709
  • 6
  • 35
  • 37
  • 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 '16 at 16:50
  • Similar question: http://stackoverflow.com/questions/7388416/what-is-the-fastest-way-to-write-fibonacci-function-in-scala – kxmh42 Sep 11 '16 at 14:30

7 Answers7

92

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!

Luigi Plinge
  • 50,650
  • 20
  • 113
  • 180
  • 1
    Ooh, I didn't know about scanLeft, that's really cool. – Tal Pressman Mar 26 '12 at 06:08
  • 7
    @LuigiPlinge Isn't this a forward reference? Only works if I apply the `lazy` keyword. – Hunter McMillen Apr 02 '13 at 03: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`. – Luigi Plinge Apr 02 '13 at 04:57
  • @LuigiPlinge Could you explain why this matters? – DCKing Apr 18 '14 at 10:13
  • 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. – Luigi Plinge Apr 18 '14 at 13:50
  • @LuigiPlinge How can we do it as a method without using the lazy keyword? – Dinesh Sep 08 '14 at 14:34
  • Why would you want to do it as a method? That would cause it to recalculate the sequence every time. Changing the "val" to "def" above will work, but you go from O(n) to O(n^2) because it needs to re-evaluate the whole sequence for each recursive call. Which is bad. – Luigi Plinge Sep 09 '14 at 02:12
  • 2
    @LuigiPlinge I understand your point but I want to learn immutable style programming in scala using this fibonacci sequence. – Dinesh Sep 10 '14 at 13:59
  • Beautiful solution, but may I know how to implement the same with `Long` type? Running `fibs(200)` is giving a negative number. Replacing `Int` with `Long` throws a compilation error. – Ébe Isaac Apr 25 '18 at 05:22
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.

Tal Pressman
  • 7,199
  • 2
  • 30
  • 33
  • Is it possible with for-comprehension construct? – nobody Mar 25 '12 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 – Luigi Plinge Mar 26 '12 at 03: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 '12 at 03: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 '12 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. – Luigi Plinge Apr 16 '12 at 17:55
  • @LuigiPlinge I would think that if it isn't lazy it would evaluate fibs, but since it's a stream it would stop the evaluation at the 3rd element. Still, making it lazy won't hurt. – Tal Pressman Apr 16 '12 at 18:18
  • Using scanLeft is a better solution. This solution will Not work for takeWhile (4000000).sum – thlim Jun 29 '16 at 12:13
  • Streams memoize their elements, so this solution will cause a lot of memory allocations and degrade performance. If we aren't going to reuse the stream, it's better to use an Iterator instead, like in this solution: http://stackoverflow.com/a/39436970/336881 – kxmh42 Sep 11 '16 at 14:29
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.

dvdnglnd
  • 81
  • 1
  • 3
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)

user unknown
  • 35,537
  • 11
  • 75
  • 121
  • 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)` – Luigi Plinge Mar 26 '12 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. – Luigi Plinge Mar 29 '12 at 03:57
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)
dimitrisli
  • 20,895
  • 12
  • 59
  • 63
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)
}
Cristian
  • 6,765
  • 7
  • 43
  • 64
0
def fib:Stream[Int] ={
  def go(f0: Int, f1:Int): Stream[Int] = {
    Stream.cons(f0,go(f1,f0+f1))
  }
  go(0,1)
}
Saddam Abu Ghaida
  • 6,381
  • 2
  • 22
  • 29