CODEWITHSUNDEEP
scalapattern-matching
Ramy
Ramy

Reputation: 21271

scala pattern matching - variable

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.

Upvotes: 1

Views: 1722

Answers (4)

Landei
Landei

Reputation: 54584

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
}

Upvotes: 2

jilen
jilen

Reputation: 5763

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

Upvotes: 13

Jamil
Jamil

Reputation: 2160

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
}

Upvotes: 1

Kipton Barros
Kipton Barros

Reputation: 21112

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)

Upvotes: 10

Related Questions