scala pattern matching - variable

Question

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.

jilen · Accepted Answer · 2011-08-29 03:18:58Z

13

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

edited Aug 29, 2011 at 3:18

answered Aug 29, 2011 at 2:25

jilen

5,7833 gold badges38 silver badges87 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ramy Over a year ago

+1 for a great answer. Can you break this down a bit for a n00b? I'm not clear on the fib.zip (and fib.tail) part.

Kipton Barros Over a year ago

@Ramy Try this at the REPL: val s = Seq(1, 2, 3); println(s.tail); println(s zip s.tail)

Kipton Barros · Accepted Answer · 2011-08-29 02:14:55Z

10

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)

edited Aug 29, 2011 at 2:14

answered Aug 29, 2011 at 2:07

Kipton Barros

21.1k4 gold badges70 silver badges81 bronze badges

Comments

Landei · Accepted Answer · 2011-08-29 07:12:35Z

2

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
}

answered Aug 29, 2011 at 7:12

Landei

54.6k13 gold badges105 silver badges195 bronze badges

1 Comment

Ramy Over a year ago

this is in fact what i was looking for val fibs = f(s-1); (fibs.head + fibs.tail.head) :: fibs I suppose it's "less functional" because of the val, but it answers the question of how to define a variable within the scope of pattern matching.

Jamil · Accepted Answer · 2011-08-29 02:26:16Z

1

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
}

edited Aug 29, 2011 at 2:26

answered Aug 29, 2011 at 2:18

Jamil

2,1601 gold badge19 silver badges20 bronze badges

Collectives™ on Stack Overflow

scala pattern matching - variable

4 Answers 4

2 Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related