Fibonacci numbers (Scala)

From LiteratePrograms

Other implementations: ALGOL 68 | Alice ML | bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | FORTRAN | Haskell | Hume | Icon | Java | JavaScript | Lisp | Logo | Lua | Mercury | OCaml | occam | Oz | Pascal | PIR | PostScript | Python | Ruby | Scala | Scheme | Sed | sh | sh, iterative | Smalltalk | T-SQL | Visual Basic .NET

Contents 1 Recursion 2 Iteration 3 Tail Recursive 4 Functional Stream 5 Simpler Stream 6 Fold Left

Recursion

The recursive definition can be translated directly into Scala as follows:

<<fibonacci_recursive.scala>>=
  def fib( n: Int): Int = n match {
    case 0 | 1 => n
    case _ => fib( n -1) + fib( n-2)
  }

Iteration

<<fibonacci_iterative.scala>>=
  def fib( n: Int) = {
    // initial values
    var a = 0    // inferred type: Int
    var b = 1    // inferred type: Int
    // function next
    // inferred result type: Pair[Int, Int]
    def next( a: Int, b: Int) = Pair( b, a + b) ;    
    var i = 0
    while( i < n) {
      // get result pair members by pattern matching
      val Pair( c, d) = next( a, b) ;
      // assign result
      a = c
      b = d
      //iterate
      i = i +1
    }
    // return 'a'
    a
  }

Tail Recursive

<<fibonacci_tail_recursive.scala>>=
  def fib( n:Int) = fib_tr( n, 1, 0) 
  def fib_tr( n: Int, b: Int, a: Int): Int = n match {
    case 0 => a 
    case _ => fib_tr( n -1, a + b, b)
  }

Functional Stream

Allows you to treat the fibonacci numbers as an infinite lazy evaluated sequence (from http://www.scala-blogs.org/2007/12/project-euler-fun-in-scala.html)

<<fibonacci_stream.scala>>=
  lazy val fib: Stream[Int] = Stream.cons(0,Stream.cons(1, fib.zip(fib.tail).map(p => p._1 + p._2)))

Or, without explicitly using Stream.cons:

  val fibs:Stream[Int] = 0 #:: 1 #:: (fibs zip fibs.tail).map{ case (a,b) => a+b }

Notice how this version could benefit from a zipWith-function like seen in Haskell (combines 2 lists using a 2-arity function).

Simpler Stream

Uses a private function fib. Faster than the functional stream.

lazy val fibs = {
  def f(a:Int,b:Int):Stream[Int] = a #:: f(b,a+b)
  f(0,1)
}

Fold Left

<<fibonacci_foldLeft.scala>>=
  def fibo (n: Int) = ((0, 1) /: (1 to n)) ((a, dummy) => (a._2, a._1 + a._2))

Download code