2
\$\begingroup\$

Let's take the famous fibonacci problem as an example but this is a generic problem. Also, taking scala as the language as it's rather feature-rich. I want to know which solution you'd prefer.

we all know that the following implementation is evil as it's not stack-safe:

//bad!
def naiveFib(n: Int): BigInt = {
  if (n <= 1)
    1
  else
    naiveFib(n - 1) + naiveFib(n - 2)
}

we can improve it and make it tail-recursive and stack-safe:

def fibStackSafe(n: Int): BigInt = {
  @tailrec
  def internally(cycles: Int, last: BigInt, next: BigInt): BigInt =
    if (cycles > 0)
      internally(cycles-1, next, last+next)
    else
      next
  internally(n - 2 , last = 1, next = 1)
}

acceptable solution. Equally acceptable, is a solution like:

def fibByEval(n: Int): BigInt = {
  def internally(cycles: Int, last: BigInt, next: BigInt): Eval[BigInt] =
    Eval.always(cycles > 0).flatMap {
      case true =>
        internally(cycles-1, next, last+next)
      case false =>
        Eval.now(next)
    }
  internally(n - 2 , last = 1, next = 1).value
}

which uses cats's Eval/Monix's Coeval (slight difference between the two, feel free to comment on your preference) which guarantees stack-safety by definition. Although an Eval-powered function can still lack heap-safety and give you memory error. It does win you a few other things too.

Here is a Stream/LazyList attempt which uses the concepts of lazy-evaluation:

def fibByZip(n: Int): BigInt = {
  def inner:Stream[Pure, BigInt] = Stream(BigInt(1)) ++ Stream(BigInt(1)) ++ (inner zip inner.tail).map{ t => t._1 + t._2 }
  inner.drop(n-1).take(1).compile.toVector.head
}

this one comes with the feature/overhead of internally "caching" the intermediate results.

Here is a more/less (depending on your point of view) readable version of the above:

def fibByScan(n: Int): BigInt = {
  def inner: Stream[Pure, BigInt] = Stream(BigInt(1)) ++ inner.scan(BigInt(1))(_ + _)
  inner.drop(n-1).take(1).compile.toVector.head
}

and finally, here is an effect-full approach which uses fs2 streams and cats's Ref:

def fibStream(n: Int): IO[Int] = {
  val internal = {
    def getNextAndUpdateRefs(twoBefore: Ref[IO, Int], oneBefore: Ref[IO, Int]): IO[Int] = for {
      last <- oneBefore.get
      lastLast <- twoBefore.get
      _ <- twoBefore.set(last)
      result = last + lastLast
      _ <- oneBefore.set(result)
    } yield result

    for {
      twoBefore <- Stream.eval(Ref.of[IO, Int](1))
      oneBefore <- Stream.eval(Ref.of[IO, Int](1))
      _ <- Stream.emits(Range(0, n-2))
      res <- Stream.eval(getNextAndUpdateRefs(twoBefore, oneBefore))
    } yield res
  }

  internal.take(n).compile.lastOrError
}

it's not pure but it's thread-safe and pretty readable.

The code starts simple but will change in the future and needs to be maintained.

  • model changing whereas instead of using the last two entries, you might need the last three elements.

  • you want to easily debug it and/or reason about it.

  • you want to easily and efficiently test it

  • the model might become numerical and non-exact so you might want to test it for more than just correctness.

  • model will become async to calculate.

  • might need to introduce parallelism.

I appreciate we should be agile and not future proof things too much, but I am interested to know which option people would go for, considering the following criteria:

  • readability
  • conciseness
  • flexibility to maintain
  • performance

feel free to mention other criteria I might be ignoring here.

\$\endgroup\$
3
  • \$\begingroup\$ Any fibonacci number can be computed in constant time O(1) using the nonrecursive formula. That would be the most efficient, most readable, most concise And most flexible implementation. Unless you need to generate entire series up to nth element. \$\endgroup\$
    – slepic
    Feb 1, 2020 at 6:23
  • 2
    \$\begingroup\$ Please see the top of the post: "Let's take the famous fibonacci problem as an example but this is a generic problem" \$\endgroup\$
    – Maths noob
    Feb 1, 2020 at 9:12
  • 1
    \$\begingroup\$ And the generic answer Is look for non-recursive ways. They Are Always better. Sometimes by miniscule amount but often much more than that. Anyway generic questions Are off topic on this site. \$\endgroup\$
    – slepic
    Feb 1, 2020 at 9:16

0

Your Answer

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