foldLeft vs foldRight vs tailrec on Scala List

Question

Assume I have a collection of c: List[T] sorted.

And I need to make aggregation with foldLeft/foldRight which outputs (List[T],List[T],List[T]), sorted. To complete this, I have 2 possibilities:

1. foldLeft, and then reverse each one of the lists (use ::, otherwise its O(n) each step)
2. foldRight and remain in the same order (use ::)

I know that foldLeft is tailrec implemented and optimized, but making O(n) more steps to reverse the collections, in this use case - which method will generate me better performance?

Assume that the op is O(1)

Example of the code:

def analyzePayload(payload: JsObject, actionRules: List[ActionRule]): InspectorReport = {
    val analyzeMode = appConfig.analyzeMode
    val (succeed, notApplicable, failed) = actionRules.foldLeft((List[RuleResult](), List[RuleResult](), List[RuleResult]())) { case ( seed @ (succeed, notApplicable, failed), actionRule) =>

      // Evaluate Single ActionRule
      def step(): (List[RuleResult], List[RuleResult], List[RuleResult]) = actionRuleService.eval(actionRule, payload) match {

        // If the result is succeed
        case EvalResult(true, _, _) => (RuleResult.fromSucceed(actionRule, appConfig.showSucceedAppData) :: succeed, notApplicable, failed)

        // If the result is notApplicable
        case EvalResult(_, missing @_ :: _, _) => (succeed, RuleResult.fromNotApplicable(actionRule, appConfig.showNotApplicableAppData, missing) :: notApplicable, failed)

        // If the result is unmatched
        case EvalResult(_, _, unmatched @_ :: _) => (succeed, notApplicable, RuleResult.fromFailed(actionRule, appConfig.showFailedAppData, unmatched) :: failed)
      }

      analyzeMode match {
        case UntilFirstSucceed => if (succeed.isEmpty) step() else seed
        case UntilFirstNotApplicable => if (notApplicable.isEmpty) step() else seed
        case UntilFirstFailed => if (failed.isEmpty) step() else seed
        case Default => step()
        case _ => throw new RuntimeException(s"Unknown mode on analyzePayload with mode = ${analyzeMode}")
      }
    }

    InspectorReport(succeed.reverse, notApplicable.reverse, failed.reverse)
  }

---

Before that, I used tailrec which made bad preformance: (why??)

 def analyzePayload(payload: JsObject, actionRules: List[ActionRule]): InspectorReport = {
    val analyzeMode = appConfig.analyzeMode

    def isCompleted(succeed: Int, notApplicable: Int, failed: Int) = {
      analyzeMode match {
        case Default => false
        case UntilFirstSucceed => if (succeed == 0) false else true
        case UntilFirstNotApplicable => if (notApplicable == 0) false else true
        case UntilFirstFailed => if (failed == 0) false else true
      }
    }

    @tailrec
    def analyzePayloadRec(rules: List[ActionRule])(succeed: List[RuleResult], notApplicable: List[RuleResult], failed: List[RuleResult]): (List[RuleResult], List[RuleResult], List[RuleResult]) = {
      if (isCompleted(succeed.size, notApplicable.size, failed.size)) (succeed, notApplicable, failed)
      else rules match {

        // Base cases:
        case Nil => (succeed, notApplicable, failed)

        // Evaluate case:
        case nextRule :: tail =>
          actionRuleService.eval(nextRule, payload) match {

          // If the result is succeed
          case EvalResult(true, _, _) => analyzePayloadRec(tail)(RuleResult.fromSucceed(nextRule, appConfig.showSucceedAppData) :: succeed, notApplicable, failed)

          // If the result is notApplicable
          case EvalResult(_, missing @_ :: _, _) => analyzePayloadRec(tail)(succeed, RuleResult.fromNotApplicable(nextRule, appConfig.showNotApplicableAppData, missing) :: notApplicable, failed)

          // If the result is unmatched
          case EvalResult(_, _, unmatched @_ :: _) => analyzePayloadRec(tail)(succeed, notApplicable, RuleResult.fromFailed(nextRule, appConfig.showFailedAppData, unmatched) :: failed)
        }
      }
    }

    analyzePayloadRec(actionRules.reverse)(Nil, Nil, Nil).toInspectorReport // todo: if the analyzeModes are not Default - consider use Streams for lazy collection
  }

Performance:

Until 22:16, this tailrec analyze was in use, then, the above code. which you can see that generates much better performance - the same data was in use.

The x-axis is timeline and y-axis is time in ms (1.4s)

Any ideas why? tailrec should be faster, that's why I consider using foldRight.

Answer 1

What makes your tailrec version slow is

isCompleted(succeed.size, notApplicable.size, failed.size)

taking the size of a linked list in Scala is linear in the size, and you're computing the size of all three lists (at least two of which you're never using (and you don't use any of them by Default)).

On the nth iteration of the tailrec, you're going to walk n list nodes between the size computations, so n iterations of tailrec is at least O(n^2).

Passing the lists themselves to isCompleted (as you effectively do in the foldLeft version) and checking isEmpty should dramatically speed things up (especially in the Default case).

Answer 2

Assuming we have those case classes:

case class InspectorReport(succeed: List[ActionRule], notApplicable: List[ActionRule], failed: List[ActionRule])
case class ActionRule()
case class EvalResult(success: Boolean, missing: List[String], unmatched: List[String])

And the evaluator:

class ActionRuleService {
  def eval(actionRule: ActionRule, payload: JsObject): EvalResult = EvalResult(true, List(), List())
}

val actionRuleService = new ActionRuleService

I would try something like this:

def analyzePayload(payload: JsObject, actionRules: List[ActionRule]): InspectorReport = {
  val evaluated = actionRules.map(actionRule => (actionRule, actionRuleService.eval(actionRule, payload)))
  val (success, failed) = evaluated.partition(_._2.success)
  val (missing, unmatched) = failed.partition(_._2.missing.nonEmpty)
  InspectorReport(success.map(_._1), missing.map(_._1), unmatched.map(_._1))
}

Or:

def analyzePayload(payload: JsObject, actionRules: List[ActionRule]): InspectorReport = {
  val evaluated = actionRules.map(actionRule => (actionRule, actionRuleService.eval(actionRule, payload)))
  val success = evaluated.collect {
    case (actionRule, EvalResult(true, _, _)) =>
      actionRule
  }
  val missing = evaluated.collect {
    case (actionRule, EvalResult(false, missing, _)) if missing.nonEmpty =>
      actionRule
  }
  val unmatched = evaluated.collect {
    case (actionRule, EvalResult(false, missing, unmatched)) if missing.isEmpty && unmatched.nonEmpty =>
      actionRule
  }
  InspectorReport(success, missing, unmatched)
}