How to return a function in scala

Question

How can I return a function side-effecting lexical closure¹ in Scala?

For instance, I was looking at this code sample in Go:

...    
// fib returns a function that returns
// successive Fibonacci numbers.
func fib() func() int {
    a, b := 0, 1
    return func() int {
        a, b = b, a+b
        return b
    }
}
...
println(f(), f(), f(), f(), f())

prints 1 2 3 5 8

And I can't figure out how to write the same in Scala.

^{1. Corrected after Apocalisp comment}

Answer 1

Slightly shorter, you don't need the return.

def fib() = {
    var a = 0
    var b = 1
    () => { 
        val t = a;
        a = b
        b = t + b
        b
    }
}

Answer 2

Gah! Mutable variables?!

val fib: Stream[Int] =
  1 #:: 1 #:: (fib zip fib.tail map Function.tupled(_+_))

You can return a literal function that gets the nth fib, for example:

val fibAt: Int => Int = fib drop _ head

EDIT: Since you asked for the functional way of "getting a different value each time you call f", here's how you would do that. This uses Scalaz's State monad:

import scalaz._
import Scalaz._

def uncons[A](s: Stream[A]) = (s.tail, s.head)
val f = state(uncons[Int])

The value f is a state transition function. Given a stream, it will return its head, and "mutate" the stream on the side by taking its tail. Note that f is totally oblivious to fib. Here's a REPL session illustrating how this works:

scala> (for { _ <- f; _ <- f; _ <- f; _ <- f; x <- f } yield x)
res29: scalaz.State[scala.collection.immutable.Stream[Int],Int] = scalaz.States$$anon$1@d53513

scala> (for { _ <- f; _ <- f; _ <- f; x <- f } yield x)
res30: scalaz.State[scala.collection.immutable.Stream[Int],Int]  = scalaz.States$$anon$1@1ad0ff8

scala> res29 ! fib
res31: Int = 5

scala> res30 ! fib
res32: Int = 3

Clearly, the value you get out depends on the number of times you call f. But this is all purely functional and therefore modular and composable. For example, we can pass any nonempty Stream, not just fib.

So you see, you can have effects without side-effects.

Answer 3

While we're sharing cool implementations of the fibonacci function that are only tangentially related to the question, here's a memoized version:

val fib: Int => BigInt = {                         
   def fibRec(f: Int => BigInt)(n: Int): BigInt = {
      if (n == 0) 1 
      else if (n == 1) 1 
      else (f(n-1) + f(n-2))                           
   }                                                     
   Memoize.Y(fibRec)
}

It uses the memoizing fixed-point combinator implemented as an answer to this question: In Scala 2.8, what type to use to store an in-memory mutable data table?

Incidentally, the implementation of the combinator suggests a slightly more explicit technique for implementing your function side-effecting lexical closure:

def fib(): () => Int = {
   var a = 0
   var b = 1
   def f(): Int = {
      val t = a;
      a = b
      b = t + b
      b
  }
  f
}

Answer 4

Got it!! after some trial and error:

def fib() : () => Int = {
    var a = 0
    var b = 1
    return (()=>{ 
        val t = a;
        a = b
        b = t + b
        b
    })
}

Testing:

val f = fib()
println(f(),f(),f(),f())

1 2 3 5 8

Answer 5

You don't need a temp var when using a tuple:

def fib() = {
  var t = (1,-1)
  () => { 
    t = (t._1 + t._2, t._1)
    t._1
  }
}

But in real life you should use Apocalisp's solution.