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.
