Is there a 'partial reduce' function in Scala?

Question

Is there a standard way of combining existing Scala collection functions to achieve the following? Or is this already defined in some popular extension library like Scalaz?

def partialReduceLeft[T](elements: List[T], nextReduction: List[T] => (T, List[T])): List[T] =
  if (elements == Nil)
    Nil
  else {
    val (reduction, residual) = nextReduction(elements)

    if (residual.length >= elements.length)
      throw new Exception("Residual collection from nextReduction function must be smaller than its input collection.")

    if (residual == Nil)
      List(reduction)
    else
      reduction :: partialReduceLeft(residual, nextReduction)
  }

The function takes a collection and applies a user-defined function which returns the first reduction, which may consume one or more elements. The method keeps going until all elements are consumed.

The resulting collection may have an equal or lower size to the input collection (I rather unscientifically call this a 'partial reduce left' - for want of knowing the exact term for this type of standard function :)).

My implementation is not tail-recursive, and to be honest, I'd much rather use someone else's code!!

Answer 1

There is similar method in scalaz: unfold.

You could implement your method using unfold this way:

def partialReduceLeft[T](elements: List[T],
                         nextReduction: List[T] => (T, List[T])): Stream[T] =
  unfold(elements){ es => es.nonEmpty option nextReduction(es) }