5 ways to solve Fibonacci in Scala – Tail Recursion, Memoization, The Pisano Period & More

One of the classic problems in order to explain Recursion in Computer Science is the typical Fibonacci Sequence, which takes its name in honor to Leonardo De Pisa, the Italian Mathematician who wrote the Liber Abaci in order to convince the public about the superiority of the Hindu-Arabic numeral system.

The Fibonacci Sequence is characterized by the fact that every number in it is equal to the sum of the preceding ones:

0, 1, 1, 2, 3, 5, 8, 13, 21….. 

The formal definition of the sequence Fn of Fibonacci numbers is:

Fn = Fn-1 + Fn-2

Where F0 = 0 and F1 = 1

We can solve this classical problem in Scala using 5 different approaches with their own advantages and disadvantages depending on how large is the Fibonacci sequence needed to get our solution.

 

Case 1: Pattern Matching
– Well suited for small numbers
– If n is big, throws Stack Overflow
– Gets really slow for n > 40 approx.

 

def fib1(n: Int): Int = n match {
   case 0 | 1 => n
   case _ => fib1(n – 1) + fib1(n – 2)
}

 

Case 2: Loop
– Handles Integer numbers (32 bit)
– Too verbose, non-idiomatic, mutable variables.

 

def fib2(n: Int): Int = {

   var first = 0
   var second = 1
   var count = 0

   while(count < n){
      val sum = first + second
      first = second
      second = sum
      count = count + 1
   }

   return first
}

 

Case 3: Tail Recursion
– Optimized by compiler

 

def fib3(n: Int): Int = {
   def fib_tail(n: Int, a: Int, b: Int): Int = n match {
      case 0 => a
      case _ => fib_tail(n – 1, b, a + b)
   }
   return fib_tail(n, 0 , 1)
}

 

Case 4: Memoization
– Optimization by Caching.
– Not suitable for big amounts.

(Substitute 185 with the amount of numbers to print)

val fib: Stream[BigInt] = 0 #:: 1 #:: fib.zip(fib.tail).map(p => p._1 + p._2)

def main(args: Array[String]){
   val s = fib take 185 mkString ” “
   print(s)
   println()
   print(fib(180))
}

 

Extra Case: The Pisano Period
– Gets the last n digits of Fibonacci with tail recursion (6 for this example)

def fib5( n : Int) : Int = {
   def fib_tail( n: Int, a:Int, b:Int): Int = n match {
      case 0 => a
      case _ => fib_tail( n-1, b, (a+b)%1000000 )
   }
   return fib_tail( n%1500000, 0, 1)
}

 

Grab the code at: Github

Advertisements

The Scala Ecosystem: Infographics

the scala ecosystem (6)

 

Frameworks

  • Play!: Play is an open source web application framework, written in Scala and Java, which follows the model–view–controller (MVC) architectural pattern. It aims to optimize developer productivity by using convention over configuration, hot code reloading and display of errors in the browser. www.playframework.com
  • Lift: Lift is an expressive framework for writing web applications. It draws upon concepts from peer frameworks such as Grails, Ruby on Rails, Seaside, Wicket and Django. It favors convention over configuration in the style of Ruby on Rails, although it does not prescribe the model–view–controller (MVC) architectural pattern. www.liftweb.net
  • Skinny: Skinny is a full-stack web app framework built on Skinny Micro. To put it simply, Skinny framework’s concept is Scala on Rails. Skinny is highly inspired by Ruby on Rails and it is optimized for sustainable productivity for Servlet-based web app development. http://skinny-framework.org/
  • Scalatra: Scalatra is a simple, accessible and free web micro-framework. It combines the power of the JVM with the beauty and brevity of Scala, helping you quickly build high-performance web sites and APIs. http://www.scalatra.org/
  • Spray: Spray is an open-source toolkit for building REST/HTTP-based integration layers on top of Scala and Akka. Being asynchronous, actor-based, fast, lightweight, modular and testable it’s a great way to connect your Scala applications to the world. http://spray.io/

Tools

  • Akka: Akka is an open-source toolkit and runtime simplifying the construction of concurrent and distributed applications on the JVM. Akka supports multiple programming models for concurrency, but it emphasizes actor-based concurrency, with inspiration drawn from Erlang. http://akka.io/
  • ScalikeJDBC: ScalikeJDBC is a tidy SQL-based DB access library for Scala developers. This library naturally wraps JDBC APIs and provides you easy-to-use and very flexible APIs. What’s more, QueryDSL makes your code type-safe and reusable. http://scalikejdbc.org/
  • ScalaJS: Scala.js is a compiler that compiles Scala source code to equivalent Javascript code. That lets you write Scala code that you can run in a web browser, or other environments (Chrome plugins, Node.js, etc.) where Javascript is supported. https://www.scala-js.org/
  • Slick: Slick is a modern database query and access library for Scala. It allows you to work with stored data almost as if you were using Scala collections while at the same time giving you full control over when a database access happens and which data is transferred.  http://slick.lightbend.com/
  • Kafka: is an open-source message broker project developed by the Apache Software Foundation written in Scala. The project aims to provide a unified, high-throughput, low-latency platform for handling real-time data feeds.  http://kafka.apache.org/

Testing

IDE’s

Live Events & Conferences

Job Websites

Useful Links & Resources

Functional Programming: Solving typical problems with Lists in Scala

Here are some solutions in Scala for typical problems with Lists that may arise when developing larger tasks, these ones can become repetitive over time and they could be used as a “recipe”. Also, they’re classic/basic problems for practice.

  •  Five different ways to create a function that returns a list of N elements:
def a(n: Int): List[Int] = List.fill(n)(1) 
def b(n: Int): List[Int] = (1 to n).toList 
def c(n: Int): List[Int] = if(n == 0) Nil else n :: c(n-1) 
def d(n: Int): List[Int] = List.tabulate(n)(n => 1) 
def e(n: Int): List[Int] = List.range(0,n)

 

  • Create a function that reverses a list without using the native Scala reverse method:
def rev(l: List[Any]): List[Any] = l match {
   case Nil => l
   case head :: tail => rev(tail) ::: List(head)
}

 

  •  Given a list, repeat each element in the list N amount of times:

def f(n: Int, ls: List[Int]): List[Int] = ls.flatMap(List.fill(n)(_))

 

  •  Filter a given list of integers and output only those values that are less than a specified value:

 

def g(delim: Int, ls: List[Int]): List[Int] = for(i <- ls if i < delim) yield i

 

 

  • For a given list with N integers, return a new list removing the elements at odd positions:
def removeOdds(ls: List[Int]): List[Int] = {ls.zipWithIndex.filter(_._2 % 2 != 0).map(_._1)}

 

  • Create a function that returns the sum of the odd elements from a list:
def sumOdds(ls: List[Int]): Int = ls.filter(x => x % 2 != 0).sum

 

  • Create a function that returns the size of a list of integers without using the native Scala length method:
def s(ls: List[Int]): Int = {
    var size = 0
    for(i <- ls) size = size + 1
    size
}