Wednesday, 23 April 2014

A neat Scala code snippet for depth aggregation

case class Price(val value: Double) extends AnyVal
case class Qty(val value: Int) extends AnyVal
case class Depth(price: Price, qty: Qty)

object Agg {
  def aggregate(in: List[Depth]) = in.foldLeft(List[Depth]())((l, c) => {
    if (l.isEmpty) List(c)
    else if (l.head.price == c.price) l updated (0, Depth(l.head.price, Qty(l.head.qty.value+c.qty.value)))
    else c +: l
  }).reverse
}

Thursday, 27 February 2014

GAs speed x10

For the astute observer, you will notice that in my previous post, there is a slight performance problem if the evaluation function is expensive. This line of code:
val sortedChromos = population.sortBy(w => evaluate(decode(w), target))
Actually, it should not be even coded like this, the evaluation should happen once, and then we should sort. That's one thing. The other thing, is that we could simply parallelise this... First time I have actually found a good usage for .par ;-) With this in mind, here is a new implementation of the above:
def parSort(population: Population): Population = {
  val parPopulation = population.par
  val evaledParPopulation = parPopulation.map(e => (e, evaluate(decode(e), target))).toList
  val sortedParPopulation = evaledParPopulation.sortBy(e => e._2).map(e => e._1)
  sortedParPopulation
}

val sortedChromos = parSort(population)
The third problem with a maximum of 2,000 iterations with the first sort/eval takes 51 seconds, with the par/sort/eval, 5 seconds :-)

Sunday, 23 February 2014

GAs in Scala

For tonight, what about a small, generic algorithm Scala lib? Let's start with some basic definition:
case class NbChromos(val nb: Int) extends AnyVal
case class NbGenes(val nb: Int) extends AnyVal
Then the core lib, an abstract class that will be implemented for specific solutions. T is the type of the underlying gene, U, the type of the target (solution) You can see the implementations for the methods cross, mutates for a gene, and the whole chromosome. The 3 methods that must be implemented for a specific problem are (1) the basic gene mutation ~~(), (2) the decoder to decode the chromosome def decoder and (3) the evaluator function def evaluator.
abstract class GA[T, U] {
  import scala.language.implicitConversions
  implicit def nbgenes2int(obj: NbGenes): Int = obj.nb
  implicit def nbchromos2int(obj: NbChromos): Int = obj.nb
  
  protected val rnd = new scala.util.Random
  protected def nextInt(upper: Int) = rnd.nextInt(upper)
  
  type Gene = T
  type Chromo = Seq[Gene]
  type Population = Seq[Chromo]
  
  def ~~(): Gene // Generates a random gene
  def ~~(gene: Gene): Gene = ~~() // Mutates a given gene
  def xx(c1: Chromo, c2: Chromo): (Chromo, Chromo) = { // Crosses two chromosomes
    require(c1.length == c2.length, s"Crossing chromos of different lengths ${c1.length} != ${c2.length}")
    val idx = nextInt(c1.length)
    val rmi = c1.length - idx
    (c1.take(idx) ++ c2.takeRight(rmi), c2.take(idx) ++ c1.takeRight(rmi))
  }
  def ~~(c: Chromo): Chromo = { // Mutates a chromosome
    val idx = nextInt(c.length)
    val mc = ~~(c(idx))
    c.take(idx) ++ List(mc) ++ c.takeRight(c.length - 1 - idx)
  }
  def ~#(nbGenes: NbGenes): Chromo = // Generates a random chromosome 
    (for(i <- 0 until nbGenes) yield ~~())
  def ~#(nbChromos: NbChromos, nbGenes: NbGenes): Population = { // Generates a random population
    val nbc = if (nbChromos%2 == 0) nbChromos.nb else 1 + nbChromos.nb // Makes sure we have an even number
    for(i <- 0 until nbc) yield ~#(nbGenes)
  }
  
  // The algorithm uses a 'decoder' (to decoded a chromo into the target),
  // an 'evaluator' to evaluate a solution towards its target
  // and a generic 'solve' method
  def decoder(chromo: Chromo): U
  def evaluator(solution: U, target: Option[U]): Double // The higher the number the worst, 0 is the best
  
  def solve(decode: Chromo => U)(evaluate: (U, Option[U]) => Double)
    (nbChromos: NbChromos, nbGenes: NbGenes, target: Option[U], crossOverRate:Double = 0.7, mutationRate:Double = 0.2, maxIterations:Double = 10000): (Chromo, U, Double) = {
    val nbBests = 2
    val initialPopulation = ~#(nbChromos, nbGenes)
    
    def ~!#(in: Population, out: Population = Seq()): Population = {
      val rndDouble = rnd.nextDouble
      
      if (in.isEmpty) out else {
        val c1h = in.head
        val rcs = in.tail
        val c2h = rcs.head
        if (rndDouble < mutationRate) { // Let's mutate
          val mc1 = ~~(c1h)
          val mc2 = ~~(c2h)
          ~!#(rcs.tail, List(mc1, mc2) ++ out)
        } else if (rndDouble < crossOverRate) {
          val cxs = xx(c1h, c2h)
          ~!#(rcs.tail, List(cxs._1, cxs._2) ++ out)
        } else
          ~!#(rcs.tail, List(c1h, c2h) ++ out)
      }
    } // crosses, mutates, or copies the population into a new population
    
    def solve(population: Population, iter: Int = 0): Chromo = {
      val sortedChromos = population.sortBy(w => evaluate(decode(w), target))
      
      if (iter > maxIterations) {
        sortedChromos(0)
      } else {
        val bests = sortedChromos.slice(0, nbBests)
        val best = bests(0)
        val bestDecoded = decode(best)
        val evaled = evaluator(bestDecoded, target)
        if (iter%1000 == 0) println(s"Current iter $iter, found $bestDecoded")
        if (evaled == 0) {
          println(s"Found a solution in $iter iterations")
          best
        } else {
          val shuffledChromos = rnd.shuffle(sortedChromos.take(sortedChromos.length-nbBests))
          val nextChromos = ~!#(shuffledChromos)
          val newPopulation = bests ++ nextChromos
          solve(newPopulation, iter+1)
        }
      }
    } // solves the problem
    
    val best = solve(initialPopulation)
    val bestDecoded = decode(best)
    val bestScore = evaluate(bestDecoded, target)
    (best, bestDecoded, bestScore)
  } // def solve
}
That is it for the "core" lib. Let's try this on 3 problems: a word finder, a formula finder and a circle fitter (like the one at the bottom of this page) Problem one: Word finder Given a random set of characters, find a target string.
package org.jts.ga

class PhraseGA extends GA[Char, String] {
  private val from = 'a'; val to = 'z'
  private def rndChar: Char = (rnd.nextInt(to-from+1)+from).toChar
  
  override def ~~(): Gene = rndChar
  override def decoder(chromo: Chromo) = chromo.map(g => g.toString).mkString
  override def evaluator(sol: String, tgt: Option[String]): Double =
    if (sol.length() != tgt.get.length()) Double.MaxValue else
      (for(i <- 0 until sol.length) yield if (sol(i).equals(tgt.get(i))) 0 else 100).sum
}

object WordFinder {
  def main(args: Array[String]): Unit = {
    val sga = new PhraseGA
    val target = "abcdefghijklmnopqrstuvwxyz"
    val targetLength = target.length
    val result = sga.solve(sga.decoder)(sga.evaluator)(NbChromos(100), NbGenes(targetLength), Some(target))
    println(s"result: $result")
  }
}
Problem two: Formula finder Given a sets of digits and operands, find a formula that results into a given number.
package org.jts.ga

import org.mvel2.MVEL

class FormulaFinder extends GA[Char, String] {
  private val digits = List('0', '1', '2', '3', '4', '5', '6', '7', '8', '9')
  private val operands = List('+', '-', '/', '*')
  private val domain = digits ++ operands
  private def rndElem = domain(rnd.nextInt(domain.length))
  
  override def ~~(): Gene = rndElem
  override def decoder(chromo: Chromo) = chromo.map(g => g.toString()).mkString
  override def evaluator(sol: String, tgt: Option[String]): Double = {
    try {
      val eval = MVEL.eval(sol+"+0.0")
      val tgtSol = eval.asInstanceOf[Double]
      val tgtAsD = tgt.get.toDouble
      Math.abs(tgtSol-tgtAsD)
    } catch {
      case t: Throwable => Double.MaxValue
    }
  }
}

object FormulaFinder {
  def main(args: Array[String]): Unit = {
    val sga = new FormulaFinder
    val target = "123456"
    val result = sga.solve(sga.decoder)(sga.evaluator)(NbChromos(100), NbGenes(9), Some(target))
    println(s"result: $result")
  }
}
Problem three: Circle Fitter Fits the bigger circle possible in an area full of circles. This problem is the one at the bottom of this page.
package org.jts.ga

case class Circle(val x: Int, val y: Int, val radius: Int) {
  val dxy = (x - radius, y - radius)
  val dwh = (radius * 2, radius * 2)
  val surface = Math.PI * radius.toDouble * radius.toDouble
  
  def dist(other: Circle) = Math.sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y))
  def intersect(other: Circle) = (radius + other.radius) > dist(other)
  
  def draw(g2d: java.awt.Graphics2D) = g2d.drawOval(dxy._1, dxy._2, dwh._1, dwh._2)
  override def toString = s"C($x, $y, $radius)"
}

case class Area(val w: Int, val h: Int, val max: Int) {
  val maxVal = Math.max(w, h)
  val rnd = new scala.util.Random
  val circles = for(i <- 0 until max) yield Circle(ni(w), ni(h), ni((w*.2).toInt))
  val nbCircles = circles.length
  
  def ni(i: Int) = rnd.nextInt(i)
  def persist2file(best: Circle) {
    val image = new java.awt.image.BufferedImage(w, h, java.awt.image.BufferedImage.TYPE_INT_ARGB)
    val g2d = image.createGraphics
    g2d.setColor(java.awt.Color.BLACK)
    circles.foreach(c => {
      c.draw(g2d)
      g2d.drawString(c.toString, c.x, c.y)
    })
    g2d.setColor(java.awt.Color.RED)
    best.draw(g2d)
    g2d.drawString(best.toString, best.x, best.y)
    javax.imageio.ImageIO.write(image, "png", new java.io.File("area.png"))
    println("Drawn circles")
  }
}

class CircleFitter(val area: Area) extends GA[Int, Circle] {
  private def rndVal = rnd.nextInt(area.maxVal)
  private val maxRadius = Math.min(area.h/2, area.w/2)
  private val maxSurface = Math.PI * maxRadius * maxRadius
  
   override def ~~(): Gene = rndVal
   override def decoder(chromo: Chromo) = Circle(chromo(0), chromo(1), chromo(2))
   override def evaluator(sol: Circle, tgt: Option[Circle]): Double = {
    // bigger the surface, the better
    val surfaceScore = Math.abs(1.0 - sol.surface / maxSurface)
    // fewer number of intersections, the better
    val nbIntersects = (for(c <- area.circles) yield if (sol.intersect(c)) 1.0 else 0.0).sum
    val interesectScore = nbIntersects / area.nbCircles
    // the solution must be strongly inside
    val insideScore = if ((sol.x-sol.radius < 0) || (sol.x+sol.radius > area.w) ||
                          (sol.y-sol.radius < 0) || (sol.y+sol.radius > area.h)) 10.0 else 0.0
    surfaceScore + interesectScore * 3.0 + insideScore
  }
}

object CircleFitter {
  def main(args: Array[String]): Unit = {
    val area = Area(800, 600, 25)
    val circleFitter = new CircleFitter(area)
    val best = circleFitter.solve(circleFitter.decoder)(circleFitter.evaluator)(NbChromos(1000), NbGenes(3), None, .7, .2, 1000)
    area.persist2file(best._2)
  }
}
Have fun.

Sunday, 1 December 2013

Dijkstra meets Scala meets ScalaFX

A quick post for an naive implementation of Dijkstra in Scala and a visual representation of the solution using FXML and ScalaFX.
I have first defined a graph and a vertex class as follows:
case class Coordinates(val x: Int, val y: Int)

class Vertex(val id: String, val coords: Coordinates) {
  def dist(v: Vertex):Double = dist(v.coords.x, v.coords.y)
  def dist(x: Int, y: Int):Double = Math.sqrt(
    Math.pow(coords.x - x, 2) + Math.pow(coords.y - y, 2))
  override def toString = s"V($id)@$coords"
}

class Graph(val vertices: Seq[Vertex], val neighbours: Map[Vertex, Seq[Vertex]]) {
  def +(v: Vertex):Graph = new Graph(v +: vertices, neighbours) // adds a vertex to the graph
  def ~(v: Vertex, n: Vertex):Graph = { // sets a neighbour relationship between two vertices
    val g = new Graph(vertices, neighbours + (v -> (neighbours(v) :+ n)))
    new Graph(g.vertices, g.neighbours + (n -> (g.neighbours(n) :+ v)))
  }
  def closest(x: Int, y: Int): Vertex = vertices.minBy( v => v.dist(x, y))
  override def toString = s"G(Vertices: $vertices, Neighbours: $neighbours)"
}
Then comes my Scala version of Dijkstra (would be nice to share your version...)
object Dijkstra {
  def run(graph: Graph, source: Vertex, target: Vertex):Seq[Vertex] = {
    val neighbours = graph.neighbours

    def dj2(u: Vertex, vs: Seq[Vertex], distances: Map[Vertex, Double], queue: Seq[Vertex],
            visited: Seq[Vertex], previous: Map[Vertex, Vertex]):
    (Map[Vertex, Double], Seq[Vertex], Seq[Vertex], Map[Vertex, Vertex]) = {
      if (!vs.isEmpty) {
        val v = vs.head
        val alt = distances(u) + u.dist(v)
        if (alt < distances(v) && !visited.contains(v)) {
          dj2(u, vs.tail, distances + (v -> alt), v +: queue, visited, previous + (v -> u))
        } else if (!vs.tail.isEmpty) {
          dj2(u, vs.tail, distances, queue, visited, previous)
        } else (distances, queue, visited, previous)
      } else (distances, queue, visited, previous)
    } // dj2

    def dj1(distances: Map[Vertex, Double], queue: Seq[Vertex], visited: Seq[Vertex], previous: Map[Vertex, Vertex]):Seq[Vertex] = {
      if (!queue.isEmpty) {
        val u:Vertex = queue.filter(v => {!visited.contains(v)}).min(Ordering.by((v:Vertex) => distances(v)))
        if (u == target) {
          sequenceSol(previous, target)
        } else {
          val res = dj2(u, neighbours(u), distances, queue.filterNot(v => v.id == u.id), u +: visited, previous)
          dj1(res._1, res._2, res._3, res._4)
        }
      } else Seq()
    } // dj1

    dj1(Map(source -> 0.0) withDefaultValue Double.MaxValue, Seq(source), Seq(), Map())
  } // dijkstra

  def sequenceSol(previous: Map[Vertex, Vertex], to: Vertex): Seq[Vertex] = {
    def helper(seq: Seq[Vertex], current: Vertex): Seq[Vertex] =
      if (previous.contains(current)) helper(previous(current) +: seq, previous(current)) else seq
    helper(Seq(to), to)
  }
}
I would like to find a simpler version.. really. The FXML is a simple file like this:
<?xml version="1.0" encoding="UTF-8"?>

<?import java.lang.*?>
<?import java.util.*?>
<?import javafx.scene.control.*?>
<?import javafx.scene.layout.*?>
<?import javafx.scene.paint.*?>

<AnchorPane id="AnchorPane" fx:id="masterAnchorPane" maxHeight="-Infinity" maxWidth="-Infinity" minHeight="-Infinity" minWidth="-Infinity" prefHeight="400.0" prefWidth="600.0" xmlns:fx="http://javafx.com/fxml/1" xmlns="http://javafx.com/javafx/2.2" fx:controller="org.jts.dijkstra.DijkstraController">
  <children>
    <BorderPane fx:id="borderPane" prefHeight="400.0" prefWidth="600.0" style="-fx-background-color: #CCFF99" AnchorPane.bottomAnchor="0.0" AnchorPane.leftAnchor="0.0" AnchorPane.rightAnchor="0.0" AnchorPane.topAnchor="0.0">
      <top>
        <FlowPane minHeight="21.0" prefHeight="21.0" prefWidth="600.0">
          <children>
            <TextField fx:id="nbNodes" alignment="CENTER_RIGHT" prefWidth="50.0" promptText="# nodes" text="100" />
            <Button fx:id="applyButton" mnemonicParsing="false" onAction="#handleApply" text="Apply" />
          </children>
        </FlowPane>
      </top>
    </BorderPane>
  </children>
</AnchorPane>
And finally the controller:
package org.jts.dijkstra

import javafx.fxml.{Initializable, FXML}
import javafx.scene.{control => jfxctrl}
import javafx.scene.{layout => jfxlyt}
import javafx.{event => jfxe}
import scalafx.scene.effect.Bloom
import scalafx.scene.paint.Color
import scalafx.scene.{layout => scxlyt}
import scalafx.scene.{control => scxctrl}
import java.net.URL
import javafx.event.EventHandler
import javafx.scene.input.MouseEvent

object Constants {
  val nodeSize = 16
  val width = 1500
  val height = 800
}

class DijkstraController extends Initializable {
  @FXML private var nbNodes: jfxctrl.TextField = null
  @FXML private var applyButton: jfxctrl.Button = null
  @FXML private var borderPane: jfxlyt.BorderPane = null
  @FXML private var masterAnchorPane: jfxlyt.AnchorPane = null

  private var scxMasterPane: scxlyt.AnchorPane = null
  private var scxPane: scxlyt.BorderPane = null
  private var scxNbNodes: scxctrl.TextField = null
  private var scxApplyButton: scxctrl.Button = null
  private var scxCanvas: scalafx.scene.canvas.Canvas = null

  private var fromVertex: Option[Vertex] = None
  private var toVertex: Option[Vertex] = None

  override def initialize(url: URL, rb: java.util.ResourceBundle) {
    require(masterAnchorPane != null, "masterAnchorPane must not be null")
    scxMasterPane = new scxlyt.AnchorPane(masterAnchorPane)

    require(nbNodes != null, "nbNodes must not be null")
    scxNbNodes = new scxctrl.TextField(nbNodes)

    require(applyButton != null, "applyButton must not be null")
    scxApplyButton  = new scxctrl.Button(applyButton)

    require(borderPane != null, "centerPane must not be null")
    scxPane = new scxlyt.BorderPane(borderPane)

    scxCanvas = new scalafx.scene.canvas.Canvas(Constants.width, Constants.height)
    scxPane.setCenter(scxCanvas)
  }

  @FXML private def handleApply(event: jfxe.ActionEvent) {
    // TODO In Future not in EDT
    val maxNodes:Integer = scxNbNodes.getText.toInt
    val width = scxCanvas.width.toInt
    val height = scxCanvas.height.toInt
    println(s"Generating random graph with $maxNodes in ($width, $height)")

    val random = new java.util.Random
    val vertices = for(i <- 0 until maxNodes) yield {
      val x = random.nextInt(width)
      val y = random.nextInt(height)
      val vertex = new Vertex(s"v-$i", Coordinates(x, y))
      vertex
    }
    println(s"Generated vertices $vertices")

    def generateNeighbours(neighbours: Map[Vertex, Seq[Vertex]], nbTimes: Int): Map[Vertex, Seq[Vertex]] = {
      if (nbTimes >= maxNodes) neighbours
      else {
        val v1 = vertices(random.nextInt(maxNodes))
        val v2 = vertices(random.nextInt(maxNodes))
        val n1 = neighbours + (v1 -> (neighbours(v1) :+ v2))
        val n2 = n1 + (v2 -> (n1(v2) :+ v1))
        generateNeighbours(n2, nbTimes + 1)
      }
    }

    val neighbours = generateNeighbours(Map() withDefaultValue Seq(), 0)
    println(s"Generated neighbours $neighbours")

    val graph = new Graph(vertices, neighbours)
    drawGraph(graph)
    addMouseEventHandler(graph)
  }

  private def drawGraph(g: Graph, sol: Seq[Vertex] = Seq()) {
    val gc = scxCanvas.getGraphicsContext2D
    gc.clearRect(0, 0, Constants.width, Constants.height)
    gc.setFill(Color.BLACK)
    gc.fillRect(0, 0, Constants.width, Constants.height)

    gc.setFill(Color.LIGHTYELLOW)
    gc.setEffect(new Bloom())
    g.vertices.foreach(v => {
      gc.fillOval(v.coords.x, v.coords.y, Constants.nodeSize, Constants.nodeSize)
    })

    gc.setEffect(null)
    val offset = Constants.nodeSize / 2
    gc.setStroke(Color.LIGHTBLUE)
    g.neighbours.foreach(t => {
      val from = t._1
      t._2.foreach(to => {
        gc.strokeLine(from.coords.x + offset, from.coords.y + offset, to.coords.x + offset, to.coords.y + offset)
        gc.setLineWidth(1.0)
      })
    })

    if (!sol.isEmpty) {
      gc.setFill(Color.RED)
      gc.setStroke(Color.GREEN)
      gc.setEffect(new Bloom())
      val from = sol(0)
      val to = sol.last
      gc.fillOval(from.coords.x, from.coords.y, Constants.nodeSize, Constants.nodeSize)
      gc.fillOval(to.coords.x, to.coords.y, Constants.nodeSize, Constants.nodeSize)
      val path = sol.sliding(2, 1)

      gc.setLineWidth(5.0)
      while(path.hasNext) {
        val subPath = path.next
        if (subPath.size == 2) {
          val f = subPath(0)
          val t = subPath(1)
          gc.strokeLine(f.coords.x + offset, f.coords.y + offset, t.coords.x + offset, t.coords.y + offset)
        }
      }
    }
  }

  private def addMouseEventHandler(g: Graph) {
    scxCanvas.addEventHandler(MouseEvent.MOUSE_CLICKED, new EventHandler[MouseEvent]() {
      override def handle(me: MouseEvent) = {
        val closestVertex = g.closest(me.getX.toInt, me.getY.toInt)
        //println(s"Original vertex: $closestVertex")
        fromVertex = Some(closestVertex)
      }
    })

    scxCanvas.addEventHandler(MouseEvent.MOUSE_MOVED, new EventHandler[MouseEvent]() {
      override def handle(me: MouseEvent) = {
        val closestVertex = g.closest(me.getX.toInt, me.getY.toInt)
        //println(s"Closest vertex: $closestVertex")
        val oldToVertex = toVertex
        toVertex = Some(closestVertex)
        if (!oldToVertex.equals(toVertex)) runDijkstra(g)
      }
    })
  }

  private def runDijkstra(g: Graph) {
    (fromVertex, toVertex) match {
      case (Some(f), Some(t)) => {
        val sol = Dijkstra.run(g, f, t)
        drawGraph(g, sol)
        println(s"Sol from $f to $t is $sol")
      }
      case _ =>
    }
  }
}
I am still trying to grasp ScalaFX - but looks ok so far. Full source code available on request. Just email me.

Monday, 28 October 2013

JavaFX

I have been very impressed with JavaFX 2. With Scene Builder and Experience Tools, one can create a fantastic UI in no time. I just love how easy it is to CSS the application, how refreshing the L&F is. If Oracle manages a successful marketing campaign, JavaFX will rock many boats... This is the blog you need to read regularly, I have decided to write all my new UIs in FX and Scala (thanks to ScalaFX)!

Wednesday, 4 September 2013

Thread affinity: small Scala code snippet

This is a piece of code that allows you to bind a task, via its task id, to a thread.
import scala.actors.threadpool.Executors
import scala.collection.concurrent.TrieMap
import scala.actors.threadpool.ExecutorService

object ThreadAffinity {
  val es = {
    val nbCores = Runtime.getRuntime.availableProcessors
    val execList = for(i <- 0 until nbCores) yield Executors.newSingleThreadExecutor
    val execStr = for(x <- Stream.continually(); y <- execList) yield y
    execStr.iterator
  }
  
  val idExecMap = TrieMap[Int, ExecutorService]()
  
  def exec(taskId: Int, task: Runnable) = idExecMap.getOrElseUpdate(taskId, es.next).execute(task)
}
I like the use of the "continually stream" that iterates over the list of pre-created threads. I also like the very handy getOrElseUpdate from TrieMap

Friday, 16 August 2013

Fibonacci in Scala: so many ways

Version 1, classic, pattern matching:
  def fibonacci_1(n: Int): Int = n match {
    case n if n <= 0 => 0
    case 1 => 1
    case _ => fibonacci_1(n - 1) + fibonacci_1(n - 2)
  }                                           
Version 2, using fold:
  def fibonacci_2(n: Int):Int = (((0, 1) /: (1 to n)) ((a, dummy) => (a._2, a._1 + a._2)))._1
Version 3, using streams:
  lazy val fibonacci_3: Stream[BigInt] = 0 #:: 1 #:: (fibonacci_3 zip fibonacci_3.tail map {case (x, y) => x + y})
Version 4, same as 1, but tail recursive:
  def fibonacci_tail_rec(n: Int, b: Int, a: Int): Int = n match {
    case 0 => a
    case _ => fibonacci_tail_rec(n - 1, a + b, b)
  }  
  def fibonacci_4(n: Int): Int = fibonacci_tail_rec(n, 1, 0)
Let's double check that they yield the same results:
  fibonacci_1(19)             //> res0: Int = 4181
  fibonacci_2(19)             //> res1: Int = 4181
  (fibonacci_3 take 20).last  //> res2: BigInt = 4181
  fibonacci_4(19)             //> res3: Int = 4181