Scalaz for function code simplification

Question

I wrote a Fibonacci function on Scalaz using bing operations. Here is my code:

import scalaz._, Scalaz._

def fib(i: Int): Option[Int] = i match {
  case 0 => 0.some
  case 1 => 1.some
  case x if x > 1 =>
    fib(i - 1) >>= {
      a => fib(i - 2) >>= {
        b => (a + b).some
      }
    }
  case _ => None
}

Is it possible to simplify it? I don't like the stuff like this a => fib(i - 2) >>= ....

Answer 1

This looks simpler, but without Scalaz:

def fib(i: Int): Option[Int] = i match {
  case 0 => 0.some //Ok, a little bit of Scalaz's syntax sugar
  case 1 => 1.some
  case x if x > 1 => for {
    a <- fib(i - 1)
    b <- fib(i - 2)
  } yield a + b
  case _ => None
}

Basically it's Haskell's do-notation, here you can see <- as a more convenient version of >>= (bind). Practically it expands to flatMap by compiler.

Scalaz can help when you need to do it for more complicated types (let's imagine you want to make it async/effectful, but still ordered) - you can use monadic transformers then. Here is the explanation from cats documentation (pretty much similar to scalaz, but much much clearer): http://typelevel.org/cats/tut/optiont.html.

When things get even more complicated (let's say you need to manage effectful computation for Future or Task along with error processing), it might help to use advanced transformers, like: https://github.com/djspiewak/emm

P.S. Do we need it all for Fibonacci? Probably not, but we can still imagine an external service for "minus" and "plus", so in that case Scalaz/Cats will help.

def minus(a: Int, b: Int): Task[Int] = Task.delay(a - b)
def plus(a: Int, b: Int): Task[Int] = Task.delay(a + b)
def fib(i: Int): Task[Option[Int]] = {...}

Which scalaz/cats can simplify (at least binding itself :) ) to:

def minus(a: Int, b: Int): OptionT[Task, String] = OptionT(Task.delay(Some(a - b)))
def plus(a: Int, b: Int): OptionT[Task, String] = OptionT(Task.delay(Some(a - b)))

and then to:

def minus(a: Int, b: Int): OptionT[Task, String] = OptionT.liftF(Task.delay(a - b))
def plus(a: Int, b: Int): OptionT[Task, String] = OptionT.liftF(Task.delay(a - b))

def fib(i: Int): OptionT[Task, String] = i match {
  case 0 => OptionT.pure(0)//OptionT.fromOption(0.some)
  case 1 => OptionT.pure(1)//OptionT.fromOption(1.some)
  case x if x > 1 => for {
    a <- fib(minus(i, 1))
    b <- fib(minus(i, 2))
    sum <- plus(a, b)
  } yield sum
  case _ => None
}

Example with error processing (scalaz/fs2 Task basically encapsulates them, but let's say you want precise types instead of Throwable)

type ServiceError = Throwable //use Xor.catchNonFatal to catch errors from external service
def minus(a: Int, b: Int): Task[Xor[ServiceError, Int]] = Task.delay((a - b).right)
def plus(a: Int, b: Int): Task[Xor[ServiceError, Int]] = Task.delay((a + b).right)
def fib(i: Int): Task[Option[Xor[ServiceError, Int]]] = {...}

Emm will simplify it to:

type ServiceError = Throwable //use Xor.catchNonFatal to catch errors from external service

//Note: you need kind-projector for that syntax: https://github.com/non/kind-projector
type E = Task |: (ServiceError \/ ?) |: Option |: Base 

def minus(a: Int, b: Int): Emm[E, Int] = ...
def plus(a: Int, b: Int): Emm[E, Int] = ...
def fib(i: Int): Emm[E, Int] = {...}

You can try complete those examples as an exercise.

P.S.2

You can also simplify pattern matching:

def fib(i: Int): Option[Int] = i match {
  case x if x < 0 => None //explicit validation comes first
  case x if x > 1 => for {
    a <- fib(i - 1)
    b <- fib(i - 2)
  } yield a + b
  case x => x.some
}

You can try to do validation with Xor/\/ as an exercise: http://typelevel.org/cats/tut/xor.html

P.S.3 Note that all of your implementation is not stack-safe (no tailrec optimization), so you might need Trampoline to compensate (depending on your real task, as fibonacci are implemented a lot easier in stack-safe way, but without error on negative number, you can basically throw an exception or return 0):

http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html

Scalaz: http://eed3si9n.com/learning-scalaz/Stackless+Scala+with+Free+Monads.html

In cats trampoline is just Free[Function0, A]: https://github.com/typelevel/cats/blob/master/free/src/main/scala/cats/free/Trampoline.scala

Talking about Task, it is actually trampolined inside, so it's safe to use it for such computations - so monadic transformers (OptionT[Task, Int]) are coming in hand here.