CODEWITHSUNDEEP
scalaoptimizationtail-recursion
user2963757
user2963757

Reputation: 107

Scala method optimization

I'm having a def that is recursively called and I'm using a bunch of cases. I'm wondering is there is any nice solution to get rid of that cases, without losing the readability of the definition.

 @tailrec
  def getElements(existent:List[List[String]], proposed: List[List[String]], result: List[(String,List[String])]): List[(String, List[String])]= {

    proposed match {
      case head :: tail => {
        existent.find(element => identicalOfMatch(element, head)) match {

          case Some(elem) => getElements(existent.filterNot(e => e == elem), tail, ("Same", elem) :: result)
          case None =>   {
            existent.find(element => noneOfMatch(element, head) && canDelete(proposed, element)) match {

              case Some(elem) => getElements(existent.filterNot(e => e == elem), head::tail, ("Delete", elem) :: result)
              case None => {
                existent.find(element => firstOfMatch(element, head)) match {

                  case Some(elem) => getElements(existent.filterNot(e => e == elem), tail, ("Update", head) :: result)
                  case None => {
                    existent.find(element => anyOfMatch(element, head) && firstOfNotPresent(proposed, head.head) && firstOfNotPresent(existent, head.head)) match {

                      case Some(elem) =>  getElements(existent.filterNot(e => e == elem), tail, ("Update", head) :: result)

                      case None =>        getElements(Nil, Nil, existent.map(element => ("Deleted", element)) ::: proposed.map(element => ("Created", element)) ::: result)
                    }
                  }
                }
              }
            }
          }
        }
      }
      case Nil => result
    }
  }

Upvotes: 1

Views: 118

Answers (1)

Krzysztof Atłasik
Krzysztof Atłasik

Reputation: 22625

Your method readability would benefit greatly if you could split it into several methods. Unfortunately, you can't do that if you want your function to be tail-recursive.

But there is a solution which is called trampoline, which would allow you to create an arbitrarily deep chain of function recursive calls which are stack-safe.

Trampolines are implemented in Scala standard library in package scala.util.control.TailCalls. I reimplemented your method to take advantage of it.

First thing I did was removing an accumulator parameter from getElements, we won't need it anymore.

Then I split getElements into three functions. I called nested functions ifNoneMatched and ifNoneMatched2 but you could probably come up with more meaningful names.

Then I wrapped every call to a function which is in the chain into tailcall and every constant into done (in our case Nil). When I needed to append something to list returned from a recursive call I used flatMap from TailRec.

import scala.util.control.TailCalls._

def getElements(existent:List[List[String]], proposed: List[List[String]]): TailRec[List[(String, List[String])]]= {

    proposed match {
      case head :: tail => {
        existent.find(element => identicalOfMatch(element, head)) match {
          case Some(elem) => tailcall(getElements(existent.filterNot(e => e == elem), tail).map(("Same", elem) :: _))
          case None => tailcall(ifNoneMatched(head, tail, existent, proposed))
        }
      }
      case Nil => done(Nil)
    }
}

def ifNoneMatched(head: List[String], tail: List[List[String]], existent:List[List[String]], proposed: List[List[String]]): TailRec[List[(String, List[String])]] = {
    existent.find(element => noneOfMatch(element, head) && canDelete(proposed, element)) match {

      case Some(elem) => tailcall(getElements(existent.filterNot(e => e == elem), proposed)).map(("Delete", elem) :: _)
      case None => tailcall(ifNoneMatched2(head, tail, existent, proposed))
    }
}

def ifNoneMatched2(head: List[String], tail: List[List[String]], existent:List[List[String]], proposed: List[List[String]]): TailRec[List[(String, List[String])]] = {
    existent.find(element => firstOfMatch(element, head)) match {

      case Some(elem) => getElements(existent.filterNot(e => e == elem), tail).map(("Update", head) :: _)
      case None => {
        existent.find(element => anyOfMatch(element, head) && firstOfNotPresent(proposed, head.head) && firstOfNotPresent(existent, head.head)) match {
          case Some(elem) =>  tailcall(getElements(existent.filterNot(e => e == elem), tail)).map(("Update", head) :: _)
          case None => getElements(Nil, Nil).map(existent.map(element => ("Deleted", element)) ::: proposed.map(element => ("Created", element)) ::: _)
        }
      }
    }
}

getElements returns now TailRec[List[(String, List[String])]], but you can unwrap it by just calling result.

Of course, you can nest methods even deeper. Until you wrap your method calls into tailcall your stack is safe.

I didn't reimplement your methods like identicalOfMatch etc. so I couldn't really test if my implementation works. If something breaks please let me know ;)

Upvotes: 1

Related Questions