5
\$\begingroup\$

I am progressing through the problems listed at projecteuler.com as I learn Scala (my blog where I am covering this experience). I have written a function to produce all the Fibonacci numbers possible in an Int (it's only 47). However, the resulting function feels imperative (not functional).

  val fibsAll = {
    //generate all 47 for an Int
    var fibs = 0 :: List()
    var current = fibs.head
    var next = 1
    var continue = true
    while (continue) {
      current = fibs.head
      fibs = next :: fibs
      continue = ((0.0 + next + current) <= Int.MaxValue)
      if (continue)
        next = next + current
    }
    fibs.reverse
  }

I am looking for feedback on this code:

  1. To what degree does the presence of even a single var (there are four here) indicate an erred approach from a functional standpoint?
  2. Given I want to return a List[Int], what better way is there to do this recursively as opposed to my current (odd) "while loop" approach?

I am finding the transition from imperative to functional thinking quite challenging.

\$\endgroup\$

2 Answers 2

6
\$\begingroup\$
object Euler002 extends App{
  // Infinite List (Stream) of Fibonacci numbers 
  def fib(a: Int = 0, b: Int = 1): Stream[Int] = Stream.cons(a, fib(b, a+b)) 

  // Take how many numbers you want into a List 
  val fibsAll = fib() takeWhile {_>=0} toList
  fibsAll reverse 
}

Take a look at this.

\$\endgroup\$
6
  • \$\begingroup\$ Tyvm for your answer. I had already found the "sum the series" answers. However, that solution doesn't work as I'm doing a modified version of the problems. So, I need the above function signature as-is; no parameters and returning all 47 values as a List[Int] in ascending order. \$\endgroup\$ Commented Jul 24, 2011 at 20:42
  • \$\begingroup\$ I modified the code to convert the stream into a list \$\endgroup\$ Commented Jul 24, 2011 at 21:51
  • \$\begingroup\$ LOL! Okay. That works. It still misses the point, though. I can't assume there are 47 values in the function (although I can in the test case validating the results).. \$\endgroup\$ Commented Jul 24, 2011 at 22:12
  • 1
    \$\begingroup\$ Use takeWhile {_>0} to get all numbers below Int.MaxValue \$\endgroup\$ Commented Jul 24, 2011 at 22:51
  • 1
    \$\begingroup\$ I prefer to use BigInt instead of Int. BigInt has no upper limit. You could redefine fibs replacing Int with BigInt. fibsAll would look like: val fibsAll = fib() takeWhile {_<Int.MaxValue} toList \$\endgroup\$ Commented Jul 24, 2011 at 23:37
6
\$\begingroup\$

What you should seek in functional programming is referential transparency. That means you can replace something with its value, and the surrounding code will still work.

For example:

var continue = true
while (continue) {

So, continue is true (at least the first time this is executed). Can I replace, then, while (continue) with while (true) and have the rest of the code work as expected? The answer is no, of course.

However, consider that this code generates a fibsAll which is a list of fibonacci numbers less than Int.MaxInt. If I replace the whole definition of fibsAll with that list, will the rest of the code act as expected? Yes, it will!

So even though you lost referential transparency in the small, you still kept it in the large. If you need to compromise on FP, this is the kind of compromise you should seek.

Having said that, there are many ways of getting around this. A while loop is often easily converted into recursion -- and, if tail recursive, recursion is as fast as, and sometimes faster than, while loops. For example:

import scala.annotation.tailrec // turns non-tail recursion into an error
val fibsAll = {
    @tailrec def recurse(current: Int, next: Int, acc: List[Int]): List[Int] =
        if (next >= current) recurse(next, next + current, current :: acc)
        else acc
    recurse(0, 1, Nil).reverse
}

A non-tail recursive version of it is simpler, and since the list is pretty small, you are unlikely to get stack overflow errors.

val fibsAll = {
    def recurse(current: Int, next: Int): List[Int] =
        if (next >= current) current :: recurse(next, next + current)
        else Nil
    recurse(0, 1)
}

Another way of thinking of it is with iterate, which produces an element based on the previous one. For Iterator (not really a functional class) and Stream, it can be infinite. With other collections, such as List, you can define a number of elements. This solution uses a Stream, and then limit it as appropriate:

val fibsAll = (
    Stream.iterate(0 -> 1){ case (a, b) => (b, a + b) }
    takeWhile { case (a, b) => b >= a }
    map { case (a, b) => a }
    toList
)

There's also unfold, which you can find on blogs and on the Scalaz library. It combines map, iterate and takeWhile in a single function:

val fibsAll = (0, 1).unfold[List, Int]{ 
    case (a, b) => 
        if (a > b) None 
        else Some(a -> (b, a + b))
}
\$\endgroup\$
1
  • \$\begingroup\$ Fantastic! That was the principle I was trying to learn, but didn't know how to ask; referential transparency! And thank you for your being so detailed in your comments. It really helped me see what you are saying concretely. And to see that if/when a compromise is needed (say for performance reasons), encapsulating the referential transparency loss within a method is the best pathway for quality software engineering. Again, tysvm for your answer. \$\endgroup\$ Commented Jul 27, 2011 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.