How can I return a function side-effecting lexical closure1 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
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
}
}
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.
error: type mismatch; found: Int; required: (Int, Int) on Scala 2.8.1. What's wrong here?
(fib zip fib.tail map Function.tupled(_+_)). More importantly, using def instead of val means this definition is not O(1).
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
}
var (a, b) = (0, 1).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
var (a, b) = (0, 1). No tupled assignment, however.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.
