Functional composition of both success and error paths

Question

TLDR: I'm looking for functional programming patterns for composing both the success and failure paths of recursive, failable functions.

Scastie link for the example code: https://scastie.scala-lang.org/apUioyJsSdaziPfiE14CoQ

Given a recursive datatype and failable method that operates on it:

sealed trait Expr
case class Lit(x: Int) extends Expr
case class Div(lhs: Expr, rhs: Expr) extends Expr

def evaluate(expr: Expr): Either[String, Int] = ???

Typical examples of functional composition show how to elegantly implement these things:

def evaluate(expr: Expr): Either[String, Int] = expr match {
  case Lit(x) => Right(x)
  case Div(l, r) =>
    for {
      x <- evaluate(l)
      y <- evaluate(r)
      res <- if (y != 0) Right(x / y) else Left("Divide by 0!")
    } yield res
}

evaluate(Div(Lit(8), Div(Lit(3), Lit(0)))) // Left("Divide by 0!")

This is great, except that sometimes you also want to do some kind of composition of the error messages. This is especially useful if you want parent nodes to add information to errors propagated from their children.

Perhaps I want to return an error message with context about the entire expression rather than just the information that there was a divide by 0 somewhere:

def evaluate2(expr: Expr): Either[String, Int] = expr match {
  case Lit(x) => Right(x)
  case Div(lhs, rhs) =>
    val l = evaluate2(lhs)
    val r = evaluate2(rhs)
    val result = for {
      x <- l
      y <- r
      res <- if (y != 0) Right(x / y) else Left(s"$x / 0")
    } yield res
    result.orElse {
      Left(s"(${l.merge}) / (${r.merge})") // take advantage of Any.toString
    }
}

evaluate2(Div(Lit(8), Div(Lit(3), Lit(0)))) // Left("(8) / (3 / 0)")

This isn't terrible, but it isn't great either. It's 4 lines of business logic vs. 5-6 of boiler plate.

Now, I'm not the best at functional programming, and I don't know much about Cats and Scalaz, but I do now that this smells like a reusable higher-order function. From the type that I want, I can derive a pretty useful utility function:

def flatMap2OrElse[R, A, B](x: Either[R, A], y: Either[R, A])
                           (f: (A, A) => Either[R, B])
                           (g: (Either[R, A], Either[R, A]) => R): Either[R, B] =
  (x, y) match {
    case (Right(a), Right(b)) => f(a, b)
    case _                    => Left(g(x, y))
  }

Then it's trivial to write a concise form:

def evaluate3(expr: Expr): Either[String, Int] = expr match {
  case Lit(x) => Right(x)
  case Div(lhs, rhs) =>
    flatMap2OrElse(evaluate3(lhs), evaluate3(rhs)) {
      (x, y) => if (y != 0) Right(x / y) else Left(s"$x / 0")
    } {
      (x, y) => s"(${x.merge}) / (${y.merge})"
    }
}

evaluate3(Div(Lit(8), Div(Lit(3), Lit(0)))) // Left("(8) / (3 / 0)")

The orElse function taking Eithers is a bit weird, but it's my function and it can be weird if I want it to.

In any case, it seems to me that there should be a pattern here. Is the style of evaluate2 the canonical way of doing it or are there utilities/abstractions I should be looking at to better handle this kind of thing?

EDIT

New Scastie: https://scastie.scala-lang.org/p0odf16PTLOTJPYSF9CGMA

This is a partial answer, but still requires a custom function that feels like it should exist somewhere. I think with just flatMap2 we can do this pretty clearly without the boutique flatMap2OrElse:

def flatMap2[R, A, B](x: Either[R, A], y: Either[R, A])
                     (f: (A, A) => Either[R, B]): Either[R, B] =
  (x, y) match {
    case (Right(a), Right(b)) => f(a, b)
    case (Left(a), _)         => Left(a) // Need Either[R, B]
    case (_, Left(b))         => Left(b)
  }

def evaluate4(expr: Expr): Either[String, Int] = expr match {
  case Lit(x) => Right(x)
  case Div(lhs, rhs) =>
    val l = evaluate4(lhs)
    val r = evaluate4(rhs)
    flatMap2(l, r)((x, y) => if (y != 0) Right(x / y) else Left(s"$x / 0"))
    .orElse(Left(s"(${l.merge}) / (${r.merge})"))
}

evaluate4(Div(Lit(8), Div(Lit(3), Lit(0)))) // Left("(8) / (3 / 0)")

That being said, this concept should generalize beyond flatMap2. It just feels like this is already a thing.

Functional composition of both success and error paths

0 Answers