CODEWITHSUNDEEP
algorithmscalafunctional-programming
sdanzig
sdanzig

Reputation: 4500

How can a "while remaining" algorithm be converted to functional style?

In my imperative-style Scala code, I have an algorithm:

def myProcessor(val items: List) {
  var numProcessed = 0
  while(numProcessed < items.size) {
    val processedSoFar = items.size - numProcessed
    numProcessed += processNextBlockOfItems(items, processedSoFar)
  }
}

I would like to keep the "block processing" functionality, and not just do a "takeWhile" on the items list. How can I rewrite this in functional style?

Upvotes: 4

Views: 147

Answers (2)

The Archetypal Paul
The Archetypal Paul

Reputation: 41749

So, this depends on what you consider to be more functional, but here's a version without the 'var'

  def myProcessorFunctional(items: List[Int]) {
    def myProcessorHelper(items: List[Int], numProcessed: Int) {
      if (numProcessed < items.size) {
        val processedSoFar = items.size - numProcessed
        myProcessorHelper(items,
            numProcessed + processNextBlockOfItems(items, processedSoFar))
      }
    }
    myProcessorHelper(items, 0)
  }

(making it a list of Ints just for simplicity, it would be easy to make it work with a generic List)

I have to say it's one of those cases where I don't mind the mutable variable - it's clear, no reference to it escapes the method.

But as I said in a comment above, processNextBlockOfItems is inherently non-functional anyway, since it's called for its side effects. A more functional way would be for it to return the state of its processing so far, and this state would be updated (and returned) on a subsequent call. Right now, if you in the middle of processing two different items lists, you'd have the issue of maintaining two different partially-processed states within processNextBlockOfItems...

Later:

Still ignoring the state issue, one convenient change would be if processNextBlockOfItems always processed the first block of the items list passed to it, returned the remaining items it had not processed (this is convenient and efficient if using List, so much so I'm wondering why you're using indicies).

This would yield something like:

  def myProcessorMoreFunctional(items: List[Int]) {
    if (!items.isEmpty) {
        myProcessorMoreFunctional(processNextBlockOfItems(items))
      }
  }

Upvotes: 1

wheaties
wheaties

Reputation: 35970

You need to change it to a recursive style wherein you "pass" in the "state" of each loop

@tailrec
def myProcessor(items: List[A], count: Int = 0): Int = items match{
  case Nil => count
  case x :: xs => 
    processNextBlockOfItems(items, count) 
    myProcessor(xs, count + 1)
}

assuming that "processedSoFar" is not an index. If you can work with the current "head" of the list:

@tailrec
def myProcessor(items: List[A], count: Int = 0): Int = items match{
  case Nil => count
  case x :: xs => 
    process(x) 
    myProcessor(xs, count + 1)
}

where process would only process the current "head" of the List.

Upvotes: 5

Related Questions