Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there a concept for 'fold with break' or 'find with accumulator' in functional programming?

Title says it all, really; iterating over collection while preserving state between loops and finishing iteration based on termination condition in addition to simply running out of elements may be the most common pattern to accomplish anything in imperative programming. It seems to me however like it's something functional gentleprogrammers agreed to not talk about, or at least I never encountered an idiom for it or a semi-standarized name such as with map, fold, reduce, etc.

I often use the followinig code in scala:

implicit class FoldWhile[T](private val items :Iterable[T]) extends AnyVal {
    def foldWhile[A](start :A)(until :A=>Boolean)(op :(A, T)=>A) :A = {
        if (until(start)) start
        else {
            var accumulator = start
            items.find{ e => accumulator = op(accumulator, e); until(accumulator) }
            accumulator
        }

    }

}

But it's ugly. Whenever I try a more declarative approach, I come with even longer and almost surely slower code, akin to:

Iterator.iterate((start, items.iterator)){
    case (acc, i) if until(acc) => (acc, i)
    case (acc, i) if i.hasNext => (op(acc, i.next()), i)
    case x => x
}.dropWhile {
    case (acc, i) => !until(acc) && i.hasNext
}.next()._1

(A more functional variant would use Lists or Streams, but iterators have arguably lesser overhead than converting items to a Stream, as default implementation for the latter uses an iterator underneath anyway).

My questions are:

1) Does this concept have a name in functional programming, and if so, what is the pattern associated with its implementation?

2) What would be the best (i.e. concise, generic, lazy, and with least overhead) way to implememnt it in scala?

like image 371
Turin Avatar asked Apr 09 '16 15:04

Turin


People also ask

How does fold work functional programming?

In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order functions that analyze a recursive data structure and through use of a given combining operation, recombine the results of recursively processing its constituent parts, building up a ...

How does fold left work?

The foldLeft method takes an associative binary operator function as parameter and will use it to collapse elements from the collection. The order for traversing the elements in the collection is from left to right and hence the name foldLeft. The foldLeft method allows you to also specify an initial value.

What is fold left and fold right?

Both methods recursively combine items into another item. foldLeft combines items from left one to right one, on the other hand foldRight does this from right one to left one.

What does fold do in Python?

Definition. Python casefold() built-in function is an aggressive lower() function that converts strings to case folded strings for caseless matching.


1 Answers

This is frowned upon by scala purists, but you can use a return statement like this:

 def foldWhile[A](zero: A)(until:A => Boolean)(op:  (A,T) => A): A = items.fold(zero) {
      case (a, b) if until(a) => return a
      case (a,b) => op(a, b)
}

Or, if you are one of those frowning, and would like a purely functional solution without dirty imperative tricks, you can use something lazy, like an iterator or a stream:

items
  .toStream // or .iterator - it doesn't really matter much in this case
  .scanLeft(zero)(op)
  .find(until)
like image 195
Dima Avatar answered Oct 04 '22 18:10

Dima