itertools

Contents

• Functions

Modules

• itertools

Module itertools

Functional iteration utilities using coroutines.

Iterators

An iterator is a coroutine which yields values of a sequence. Unless specified otherwise, iterators use a constant amount of memory, and yielding the a value takes a constant O(1) amount of time.

Typically iterator implementations use the following pattern:

function iter (...)
  -- Do one-time initialization tasks.
  local finished_iterating = false
  -- Return a coroutine.
  return coroutine.wrap(function ()
    while not finished_iterating do
      local value = calculate_next_value()
      coroutine.yield(value)
    end
  end)
end

Consuming an iterator is most conveniently done using a for-loop:

for element in iterable do
  -- Do something with the element.
end

Credits

This module is loosely based on Python's itertools module, plus some other of Python's built-ins like map() and filter().

Functions

keys (table)	Iterate over the keys of a table.
values (table)	Iterate over the values of a table.
items (table)	Iterate over the key and value pairs of a table.
each (table)	Iterate over each value of an array-like table.
collect (iterable)	Consume an iterable and collect its elements into an array-like table.
count ([n[, step]])	Iterate over an infinite sequence of consecutive numbers.
cycle (iterable)	Iterate over a sequence of elements repeatedly.
value (value[, times])	Iterate over the same value repeatedly.
islice (iterable[, start[, stop]])	Iterate over selected values of an iterable.
takewhile (predicate, iterable)	Iterate over values while a predicate is true.
map (func, iterable)	Iterate over elements applying a function to them
filter (predicate, iterable)	Iterate elements, filtering them according to a predicate.
sorted (iterable[, key[, reverse]])	Iterate over the sorted elements from an iterable.

Functions

keys (table)

Iterate over the keys of a table.

Given a table, returns an iterator over its keys, as returned by pairs.

Parameters:

• table A dictionary-like table.

Returns:

coroutine An iterator over the table keys.

values (table)

Iterate over the values of a table.

Given a table, returns an iterator over its values, as returned by pairs.

Parameters:

• table A dictionary-like table.

Returns:

coroutine An iterator over the table values.

items (table)

Iterate over the key and value pairs of a table.

Given a table, returns an iterator over its keys and values, as returned by pairs. Each yielded element is a two-element { key, value } array-like table.

Note that yielded array-like tables are not guaranteed be be unique, and if you need to save a copy of it you must create a new table yourself:

local pairs = {}
for pair in iterable do
  table.insert(pairs, { pair[1], pair[2] })
end

Parameters:

• table A dictionary-like table.

Returns:

coroutine An iterator over { key, value } pairs.

each (table)

Iterate over each value of an array-like table.

Given an array-like table, returns an iterator over its values, as returned by ipairs.

Parameters:

• table An array-like table.

Returns:

coroutine An iterator over the table values.

collect (iterable)

Consume an iterable and collect its elements into an array-like table.

Note that this function runs in O(n) time and memory usage because it needs to store all the elements yielded by the iterable.

Parameters:

• iterable coroutine A non-infinite iterator.

Returns:

1. table Array-like table with the collected elements.
2. integer Number of elements collected.

count ([n[, step]])

Iterate over an infinite sequence of consecutive numbers.

Returns an iterable which produces an infinite sequence of numbers starting at n, adding step to it in each iteration. Let i be the current iteration, starting with i = 0, the sequence generated would be:

n + step * 0, n + step * 1, n + step * 2, ..., n + step * i

Parameters:

• n number First value in the sequence. (optional)
• step number Increment added in each iteration. (optional)

Returns:

coroutine An iterator over the sequence of numbers.

cycle (iterable)

Iterate over a sequence of elements repeatedly.

Returns an iterable which produces an infinite sequence of elements: first, the elements from iterable, then the sequence is repeated indefinitely.

Note that this may store in memory up to as much elements as provided by iterable.

Parameters:

• iterable coroutine An iterator.

Returns:

coroutine An infinite iterator repeating elements from iterable.

value (value[, times])

Iterate over the same value repeatedly.

Returns an iterator which always produces the same value, indefinitely or up to a given number of times.

Parameters:

• value The value to produce.
• times integer Number of repetitions. (optional)

Returns:

coroutine An iterator which always produces value.

islice (iterable[, start[, stop]])

Iterate over selected values of an iterable.

If start is specified, the returned iterator will skip all preceding elements; otherwise start defaults to 1. The elements with indexes between start and stop (inclusive) will be yielded. If stop is not specified, the default is to yield all elements from iterable until it is exhausted.

For example, using only stop can be used to limit the amount of elements yielded by an indefinite iterator. A range() iterator similar to Python's could be implemented as follows:

function range (n)
   return itertools.islice(itertools.count(), nil, n)
end

Parameters:

• iterable coroutine An iterator.
• start integer Index of the first element, by default 1. (optional)
• stop integer Index of the last element, by default undefined. (optional)

Returns:

coroutine An iterator which selects values.

takewhile (predicate, iterable)

Iterate over values while a predicate is true.

The returned iterator returns successive elements from an iterable as long as the predicate evaluates to true for each element.

Parameters:

• predicate function Function which checks the predicate.
• iterable coroutine An iterator.

Returns:

coroutine An iterator which yield values while the predicate is true.

map (func, iterable)

Iterate over elements applying a function to them

Parameters:

• func function function Function applied to each element.
• iterable coroutine An iterator.

Returns:

coroutine An iterator which yields the results of applying the function to the elements of iterable.

filter (predicate, iterable)

Iterate elements, filtering them according to a predicate.

Returns an iterator over the elements another iterable which yields only the elements for which the predicate function return true.

For example, the following returns an indefinite iterator over the even natural numbers:

function even_naturals ()
   return itertools.filter(function (x) return x % 2 == 1 end,
                           itertools.count())
end

Parameters:

• predicate function
• iterable coroutine An iterator.

Returns:

coroutine An iterator over the elements which satisfy the predicate.

sorted (iterable[, key[, reverse]])

Iterate over the sorted elements from an iterable.

A custom key function can be supplied, and it will be applied to each element being compared to obtain a sorting key, which will be the values used for comparisons when sorting. The reverse flag can be set to sort the elements in descending order.

Note that iterable must be consumed before sorting, so the returned iterator runs in O(n) memory space. Sorting is done internally using table.sort.

Parameters:

• iterable coroutine An iterator.
• key function Function used to retrieve the sorting key used to compare elements. (optional)
• reverse boolean Whether to yield the elements in reverse (descending) order. If not supplied, defaults to false. (optional)

Returns:

coroutine An iterator over the sorted elements.