scala pattern matching - variable

1
votes

While I was reading this (page 14) I came across this algorithm:

function fib2(n)
    if n = 0 return 0
    create an array f[0 : : : n]
    f[0] = 0, f[1] = 1
    for i = 2 : : : n:
        f[i] = f[i  1] + f[i  2]
    return f[n]

If I wanted to implement this in Scala using pattern matching, is there a way to create a List in the pattern match part in order to use it in the final return statement?

these are great answers, but I think I'd still like to know if it's possible to define a variable that you only use in your pattern match. I know you can do it in Haskell, but I'm wondering if it's doable in Scala.

4
scalapattern-matching

4 Answers

2
votes

Here is a refactoring of jeela's solution. I think it's better to work always with the head, as it is much faster. The final reverse doesn't hurt much. 

def fib(s:Int) = {
  def f(s:Int):List[Int] = s match {
    case x if x < 0 => Nil
    case 0 => List(0)
    case 1 => List(1,0)
    case _ => val fibs = f(s-1); (fibs.head + fibs.tail.head) :: fibs
  }
  f(s).reverse
}
13
votes
lazy val fib: Stream[Int] = Stream.cons(0,Stream.cons(1, fib.zip(fib.tail).map(p => p._1 + p._2)))

fib.take(n).last will return the result
another stream based solution. It defines a infinite Fibonacci sequence. Yes it is rescue and infinite definition, but all computations are performed while take is called.
enter image description here just check here for more interesting code. link

10
votes

I don't see much need for pattern matching here. The straightforward translation to Scala would look basically the same: create an array f and loop over indices 2 until n.

def fib(n: Int): Array[Int] = {
  val f = new Array[Int](math.max(2, n))
  f(0) = 0
  f(1) = 1
  for (i <- 2 until n)
    f(i) = f(i-1) + f(i-2)
  f
}

If you want to get fancier, how about a lazy stream?

def fibFrom(a: Int, b: Int): Stream[Int] = a #:: fibFrom(b, a + b)
fibFrom(0, 1).take(8).toList // returns List(0, 1, 1, 2, 3, 5, 8, 13)
1
votes

I think using lazy streams is better approach but just to flex my muscles:

def fib(s:Int):List[Int] = s match {
  case 0 => Nil
  case 1 => 0::fib(s-1)
  case 2 => 0::1::fib(s-2)
  case _ => fib(s-1):::fib(s-1).takeRight(2).sum::Nil
}