Fold functions

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

Built-ins

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() 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 built-ins!

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 minimum 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().

  • nth_combination(), creates the nth combination from the elements in the iterable without having to create the previous combinations.

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.

References