Fold functions

Fold functions [0] reduce an iterable to a single value.

Builtins

There are several instances of fold functions Python library:

  • all(), reduces the iterable based on the truthiness of all elements.
  • any(), reduces the iterable based on the truthiness of all elements.
  • len(), reduces the iterable to the number of all elements. Does not work with generators!
  • max(), reduces the iterable to the maximum of all elements.
  • min(), reduces the iterable to the minimum of all elements.
  • sum(), reduces the iterable to the sum of all elements.

and also several fold operators:

  • the boolean and and or operator.
  • the mathematical operators +, -, *, /, //, % and **.
  • the bitwise operators <<, >>, |, ^ and &.
  • the comparison operators <, <=, ==, !=, >=, >.

Builtin Library functions

  • functools.reduce() (in Python 2 part of the builtins), reduces the iterable by successivly applying a binary function.

functools.reduce() is probably the most general function that could be used to recreate all the builtin functions. For example:

  • reduce(lambda x, y: x and y, iterable) is equivalent to all()
  • reduce(lambda x, y: x or y, iterable) is equivalent to any()
  • reduce(lambda x, y: x + y, iterable) is equivalent to sum()
  • reduce(lambda x, y: x if x < y else y, iterable) is equivalent to min()
  • reduce(lambda x, y: x if x > y else y, iterable) is equivalent to max()
  • reduce(lambda x, y: x + 1, iterable, 0) is equivalent to len()

Warning

These functools.reduce() functions are much slower than the builtins!

There are several other fold functions in the standard library and in third-party packages, most notably:

Additional

The iteration_utilities package includes some additional fold functions:

  • all_distinct(), reduces the iterable to a boolean value indicating if all the items are distinct.
  • all_equal(), reduces the iterable to a boolean value indicating if all the items are equal.
  • all_monotone(), reduces the iterable to a boolean value indicating if all the items are (strictly) bigger or smaller than their predecessor.
  • argmax(), reduces the iterable to the index of the maximum.
  • argmin(), reduces the iterable to the index of the minimum.
  • count_items(), reduces the iterable to the number of (matching) items.
  • minmax(), reduces the iterable to a tuple containing the mimumum and maximum value.
  • nth(), reduces the iterable to it’s nth value.
  • first(), reduces the iterable to it’s first value. See also nth().
  • second(), reduces the iterable to it’s second value. See also nth().
  • third(), reduces the iterable to it’s third value. See also nth().
  • last(), reduces the iterable to it’s last value. See also nth().

Helper functions

Included in the iteration_utilities package are several helper functions that are based on normal Python code but chosen to evaluate faster than alternatives:

Fold to other data structure

Most fold functions reduce an iterable by discarding most of the iterable. However iteration_utilities includes functions that discard no elements or only a few:

  • argsorted(), create a list of indices that would sort the iterable.
  • groupedby(), create a dictionary containing lists representing the groups of values of the iterable.
  • heapq.nlargest(), create a list containing the n largest items.
  • heapq.nsmallest(), create a list containing the n smallest items.
  • partition(), create a list containing the items which do not fulfill some predicate and one containing the items that do.
  • sorted(), create a sorted list from an iterable.

This list contains some builtin Python functions for completeness.

Short-circuit functions

Short-circuit functions [5] stop as soon as the exit condition is met. These functions can yield significant speedups over functions that eagerly process the operand.

There are several instances of short-circuit functions Python library:

  • all(), stops as soon as one item in the iterable is falsy.
  • any(), stops as soon as one item in the iterable is truthy.
  • next(), get the next item of an iterable.

and also two short-circuit operators:

  • and, evaluates the right side only if the left side is truthy.
  • or, evaluates the right side only if the left side is falsy.

iteration_utilities includes some additional short-circuit functions:

  • all_distinct(), stops as soon as a duplicate item is found.
  • all_equal(), stops as soon as a deviating item is found.
  • all_monotone(), stops as soon as a item is found violating monotony.
  • one(), get the one and only item of an iterable.
  • nth(), stops after the nth item.
  • first(), like nth() this function stops after the first item.
  • second(), like nth() this function stops after the second item.
  • third(), like nth() this function stops after the third item.

Included in the iteration_utilities package are several helper functions that are based on normal Python code but chosen to evaluate faster than alternatives:

  • all_isinstance(), stops as soon as one item is not an instance of the specified types.
  • any_isinstance(), stops as soon as one item is an instance of the specified types.