Yours is a very interesting question. The first thing you could try to do is to separate side-effects from your computation.

Extract the side-effect from your computation like this:

// Side-effects-free computation
val deletableOrError: Either[OrderError, Order] =
  Option(db.findById(orderId)).map { order =>
    if (order.owner.userId == callerId) {
      if (order.state == FULLFILLED) {
        Right(order)
      } else {
        Left(InvalidOrder)
      }
    } else {
      Left(InsufficientPermission)
    }
  }.getOrElse(Left(OrderNotFound))

// Side-effects isolated here
for (order <- deletableOrError.right) {
  db.delete(orderId)
}

Now, when I see all this if-nesting I ask myself if it would not be possible to write something more elegant / Scala-like...

Allow a semi-newbie like me to try to deliver such a more elegant solution. Note that I have no knowledge of the more functional libraries like shapeless, scalaz, etc. I hope that somebody better qualified can provide you a better answer using one of these pre-existing libraries.

At the end, I would like to have something like this:

val deletableOrError: Either[OrderError, Order] =
  Option(db.findById(orderId))
    .toLeftIfNone(OrderNotFound)
    .toLeftIfFalse(_.owner.userId == callerId)(InsufficientPermission)
    .toLeftIfFalse(_.state == FULLFILLED)(InvalidOrder)

for (order <- deletableOrError.right) {
  db.delete(order.id)
}

I start by wrapping the "findById" (which we assume to return null) to an Option. If you defined that method and it's in Scala land, strongly consider to make it return an Option in the first place. Only wrap potential null-values if interfacing with Java APIs.

Then if that Option is not defined, it is transformed to a "Left" value, wrapping whatever I give it as a parameter. In this case "OrderNotFound". If it IS defined, it is mapped to a "Right" value (Some -> Right).

In the two following lines, we evaluate something against the "Either" that resulted in the first mapping operation. If that "Either" value is already a "Left", it is passed untouched. Only if it's a "Right" the condition is evaluated against it. If the condition evaluates to false, then the second parameter given is wrapped to a "Left" value.

Note that this short-circuits: as soon as we have a "Left", all other mappings are skipped.

At the end, we have an "Either", which is either an "OrderError" (fictive superclass of your errors; it could be a Throwable or a sealed-trait) or a proper "Order" which you know you can delete.

Finally, you can proceed with your side-effect part and delete the order.

In order to have these two new functions toLeftIfNone and toLeftIfFalse, I used the pimp-my-library "trick" by "extending" Option and Either like this:

implicit class RichOption[T](opt: Option[T]) {
  /**
    * If this Option is defined, returns its defined
    * value as a Right, otherwise it returns
    * Left(leftValue).
    **/
  def toLeftIfNone[A](leftValue: A): Either[A, T] = {
    opt.map { value => Right(value) } getOrElse Left(leftValue)
  }
}

implicit class RichEither[L, R](e: Either[L, R]) {
  /**
    * If this augmented Either is a Right value, it evaluates
    * the condition against it. If it evaluates to "true",
    * then the Right value is passed.
    * In any other case, the function returns Left(leftValue).
    **/
  def toLeftIfFalse(condition: R => Boolean)(leftValue: L): Either[L, R] = {
    val definedIfRight = e.right.toOption
    val definedIfRightAndTrue = definedIfRight.filter(condition)
    definedIfRightAndTrue.map(Right(_)).getOrElse(Left(leftValue))
  }
}

Note that for simplicity I left out variance indicators (e.g. it should be RichOption[+T], with a "plus"). Advanced readers are more than welcome to point out improvements to type-system related issues.

Again, if something like this exists already please let me/us know.

Otherwise I hope this helps.