How to handle Option in recursive functions in functional programming within Scala?

user_6614559 0
Viewed 166

I recently picked up interests in functional programming, and I'm working with some toy script.

One example is, taking a list of integers, adding them up in sequence, and get the index when the rolling sum reaches a certain value, say -1.

This is what I have now:

@tailrec
def someFunc(currentSum: Int, list: List[Int], index: Int): Int = {
  if (currentSum == -1) return index
  // Return -1 if the value is never reached
  if (index >= list.length) return -1
  val value = list(index)
  someFunc(currentSum + value, list, index + 1)
}

This works, and if the rolling sum never reaches -1, function will return -1.

I'm not exactly happy with returning -1 in this case, after some readings, I was introduced to the concept of Option, basically I could have Some value or None. I figured this might be the proper solution in this scenario, so I changed my code to this:

@tailrec
def someFunc(currentSum: Int, list: List[Int], index: Int): Option[Int] = {
  if (currentSum == -1) return Some(index)
  if (index >= list.length) return None
  val value = list(index)
  someFunc(currentSum + value, list, index + 1)
}

Now my question is, is there anything I can do to avoid adding Some(index) in the 3rd line? In this case it seems trivial, but for more complex situation, it seems a bit unnecessary to add Some everywhere down in the chain.

Also I'm also wondering if this is the proper functional way to handle this type of situation?

option-type scala functional-programming
2 Answers

What you are asking is this: ""I should just be able type return index instead of typing return Some(index), and scala-compiler should understand that since this function returns a Option, so I actually mean the latter"".

it seems a bit unnecessary to add Some everywhere

It is not unnecessary. If what you ask is fulfilled, this will result in ambiguity. Consider this scenario:

def hypotheticalFunction(....): Option[Option[Int]]: = {
  if (some-condition ) return None --> ambigious
  // more code
}

Does the return None mean return Some(None) or return None? We have no way of knowing.

==========================================

Also I'm also wondering if this is the proper functional way to handle this type of situation?

I can think of at least 2 improvements:

  1. Generally return statements are discouraged, code-readability can take a setback by arbitrary breaking of function flow by a return. You can use this:
if (condition) Some(index)
else if (condition) None
else { 

}
  1. Since earlier parts of list is not needed in recursive calls, you can only send the tail of the the list to the recursive function. In this way, you won't have to iterate the list by calling list(index). Some snippet:
@tailrec
def someFunc(currentSum: Int, list: List[Int], index: Int): Option[Int] = {
  if (currentSum == -1) Some(index)
  else if (list.isEmpty) None
  else {
    val value = list.head
    someFunc(currentSum + value, list.tail, index + 1)
  }
}
user_24648220

Not sure what you mean by "everywhere down the chain". There are pretty much just two cases - either Some or None. And yeah, you have to specify which is which.

A pattern match can make this case separation a bit clearer (it also fixes a problem with your implementation making it quadratic: List is a link list, and list(index) is linear, don't do that):

def someFunc(
  list: List[Int], 
  currentSum: Int = 0,
  index: Int=0
): Option[Int] = list match {
   case _ if currentSum == -1 => Some(index)
   case Nil => None
   case head :: tail => someFunc(tail, currentSum + head, index+1)
}
user_42545170
Related