iter

Overview

A collection of useful functions for working with iterators and iterable objects.

There are two contracts which are used extensively throughout the Sano library: the iterable contract and the map-iterable contract.

An object, a, satisfies the iterable contract if:

  1. It is an iterator function, for instance: a = iter.count(10)
  2. It is an object with an 'iter' method: a = Vector:make{1,2,3,4,5}
  3. It is a vanilla Lua table, for example: a = {1,2,3,4,5}
  4. It is a string, i.e. a = "hello world!"

Nearly all library functions which operate on sequences of elements will work for any object which satisfies the iterable contract. For example, the function ordering.first takes as input an iterable object and returns the element that would appear first if the iterable object were to be sorted:

> a1 = iter.count(5,1,-1)
> a2 = {4,3,5,2,1}
> a3 = Vector:make(4,3,5,2,1)
> a4 = "fhazqe"
> print(ordering.first(a1), ordering.first(a2), 
>>      ordering.first(a3), ordering.first(a4))
1       1       1       a

As another example, the SkipSet value constructor can take any iterable as an argument:

> a = SkipSet:make(iter.count(5,1,-1))
> print(a)
{1, 2, 3, 4, 5}
> print(SkipSet:make(a))
{1, 2, 3, 4, 5}
> print(SkipSet:make{1,2,3,4,5})
{1, 2, 3, 4, 5}
> print(SkipSet:make("fhaayejvbad"))
{"a", "b", "d", "e", "f", "h", "j", "v", "y"}

An object, a, satisfies the map-iterable contract if:

  1. It is an iterator function which returns two values per step: iter.zip("abc",{1,2,3})
  2. It is an object whose 'iter' method returns a function satisfying 1.
  3. It is a vanilla Lua table, for instance a = {a=1,b=2,c=3}

Any function which expects a map-iterable object will work for any object which satisfies the map-iterable contract. For example, the HashMap value constructor can take any map-iterable as an argument:

> a = HashMap:make {a=1,b=2,c=3}; print(a)
{a=1, c=3, b=2}
> print( HashMap:make(a) ) -- make a copy of a
{a=1, c=3, b=2}
> print( HashMap:make(iter.zip("abc",{1,2,3})) )
{a=1, c=3, b=2}

Summary

makeCreates an iterable from the supplied function, or simply returns func if it is already a object with an iter method.
EMPTYAn empty iteration.
__callReturns an iterator extracted from the supplied object.
autofoldingTurn any binary function into a function which operates on a variable number of arguments, by cascading the results.
buffer...
chainReturns an iterator that is the chaining together of each iterable passed as an argument to this function.
collapseEqReturns an iterator in which adjacent duplicate elements are removed.
countReturns an iterator which counts off successive integers in the range [start..stop] with stepsize step.
cross...
enumDecorates another iteration to return the index of each element returned from the decorated iteration.
equalsReturns true if both iterations return the same number of elements and each pair of corresponding elements are equal according to equalsFn (default '==').
everyNth...
exchangeSwaps the order that multiple values are returned by two-element iterator.
filterReturns an iteration containing only the elements of iterable for which filter returns true.
findReturns the first object, e from iterable for which predicate(e) returns true, or nil if there are no matches.
firstReturns the first element of iterable if k is unspecified, or an iterator over the first k elements.
foldAlso sometimes called 'reduce' in functional programming contexts.
foldIterSame as fold, except that intermediate values are returned as an iterator.
__callReturns an iterator extracted from the supplied object.
groupEqReturns an iterator over lists of adjacent elements that are equal according to the supplied equals function (default uses '==').
interleaveReturns an iteration which alternates between returning elements from iter1 and iter2.
lastReturns the last element in the iteration over iterable.
loopReturns an iterator which cycles the iterable through times repetitions, or forever, if times is nil.
mapReturns an iteration in which each element e, in iterable, is replaced by transform(e).
mapFilter...
mapIterExtracts a 2-value iterator from obj.
mapNReturns the result of iter.map(iter.count(n), transform).
multiEqualsCompares two iterators that return multiple values for equality.
noCycle...
openFilter...
packReturns an iterator which packs the result(s) of each iteration step of iter(iterable) into a table.
pairs...
pairsToStringReturns a comma-delimted string of the key-value pairs in iterable; each pair of items (a,b) returned by iterable will be denoted by a=b in the returned string.
pipe...
pipeIter...
preorder...
repeatCallReturns an iterator which calls the function fn n times with the arguments (...).
restartable...
resume...
reverseReturns an iterator that yields elements in the reverse order of iterable.
serialize...
toListConverts an iterable to a Lua table.
toStringReturns a comma+space-delimited string of the elements in iterable, or uses the delimiter if one is provided.
transpose...
trimReturns an iterator which ignores the first count elements of iterable.
unaryReturns an 'iterator' over a single element.
windowsReturns an iteration in which each step returns size elements in a 'moving window' of the iteration.
zip'Zips' multiple iterations up into one, similar to the built-in python 'zip' function.

Detail

iter.make(func)

Creates an iterable from the supplied function, or simply returns func if it is already a object with an iter method.

iter.EMPTY

An empty iteration.

iter(obj)

Returns an iterator extracted from the supplied object.

There are four cases, each of which is handled differently:

  1. If obj is a function, this function assumes it is an iterator and returns it.
  2. If obj is a string, this function returns an iterator over the characters of the string.
  3. If obj is a table with an 'iter' field, this function returns obj:iter().
  4. If obj is a table without an 'iter' field, this function returns an iterator over the values of the table, using ipairs()

So, the loop, for e in iter(a) do ... end, works so long as a is one of the types handled by the above cases.

synonyms: iter.from

iter.autofolding(func, seed, thirdArg)

Turn any binary function into a function which operates on a variable number of arguments, by cascading the results.

Example:

function add(x,y) return x + y end
  sum = autofolding(add)
  print(sum(1,2,3,4)) --> 10
  print(sum(iter.count(4)) --> 10

buffer

iter.chain(...)

Returns an iterator that is the chaining together of each iterable passed as an argument to this function.

If only one argument is passed to this function, it is assumed to be an iterable over iterables.

Examples:

chain{ {1,1,1},{2},{3} } --> 1, 1, 1, 2, 3
chain( {1,1,1}, {2}, {3} ) --> 1, 1, 1, 2, 3
chain(iter.count(1,3), iter.count(3,6)) --> 1, 2, 3, 3, 4, 5, 6

iter.collapseEq(iterable, equalsFn)

Returns an iterator in which adjacent duplicate elements are removed.

iter.count(start, stop, step)

Returns an iterator which counts off successive integers in the range [start..stop] with stepsize step.

This function has several defaults:

If start > stop and step is positive, the iteration returned will be EMPTY. Likewise if start < stop and step is negative. Thus there is no way to accidentally construct a count iterator which does not terminate (these semantics are much like the Lua numeric for loop).

Examples:

count(4) --> 1  2  3  4
  count(-4) --> empty
  count(1,-4) --> empty
  count(2,4) --> 2  3  4
  count(4,2) --> empty 
  count(1,10,2) --> 1  3  5  7  9
  count(10,1,-2) --> 10  8  6  4  2

cross

iter.enum(iterable [, size, stop, step])

Decorates another iteration to return the index of each element returned from the decorated iteration.

If iterable is an object with a size() method, or if size is explicitly specified, the iteration will halt after iterable:size() steps. Otherwise, the iteration halts as soon as iter(iterable) halts (this may be undesireable if the iteration is expected to contain nil values)

If 2 args are given the indices will range from 1 to arg[2]. If 3 args are given the second and third arguments are interpreted as a counting range for the enumeration; If a 4th argument is specified, args 2 and 3 specify the counting range, and arg 4 specifies the step increment.

Examples:

> for ind,v in vector("abcd"):enum() do print(ind,v) end
1       a
2       b
3       c
4       d
> vec = vector("abc"); vec:add(nil)
> for ind,v in vec:enum() do print(ind, v) end
1       a
2       b
3       c
4       nil

iter.equals(iter1, iter2, equalsFn)

Returns true if both iterations return the same number of elements and each pair of corresponding elements are equal according to equalsFn (default '==').

everyNth

iter.exchange(iterable)

Swaps the order that multiple values are returned by two-element iterator.

Example:

-- i = 1,a  2,b  3,c 
iter.exchange(i) --> a,1  b,2  c,3

iter.filter(iterable, filter [,removed])

Returns an iteration containing only the elements of iterable for which filter returns true.

For each element, e which is removed from the returned iteration, removed(e) is called if removed is specified. The filtering is 'lazy', so the filtered iteration is not determined until the returned iteration is exhausted.

Example:

function isEven(n) return math.mod(n,2)==0 end
iter.filter(count(10), isEven) --> 2, 4, 6, 8, 10

iter.find(iterable, predicate)

Returns the first object, e from iterable for which predicate(e) returns true, or nil if there are no matches.

iter.first(iterable [,k])

Returns the first element of iterable if k is unspecified, or an iterator over the first k elements.

iter.fold(iterable, fn [, seed, thirdArg])

Also sometimes called 'reduce' in functional programming contexts.

fn is a binary function. Label the elements of iterable i1, i2...iN. fold calls fn(i1, i2) and passes the result to fn(_, i3), then passes the result of that to fn(_, i4) and so on. The result of the last call to fn(_, iN) is this function's return value.

Some examples:

> function sum(t) return iter.fold(t, function(a,b) return a+b end) end
> print(sum{1,2,3,4,5})
15
>  -- compute the smallest element in an iterable
>  function first(iterable, orderFn)
>>   return iter.fold(iterable, orderFn or ordering.INCREASING)
>> end
> v = vector(iter.count(100)):shuffle()
> print(first(v), first(v,ordering.DECREASING))
1       100

param func: a binary function param seed: the first element supplied to the folding process; if nil defaults to the first element in iterable param thirdArg: passed as the third argument to func at each stage of the fold

iter.foldIter(iterable, func [, seed, thirdArg])

Same as fold, except that intermediate values are returned as an iterator.

Example:

add = function(a,b) return a+b end
sums = iter.toList(iter.foldSeq({1,2,3,4,5}, add)) --> [3,6,10,15]

iter(obj)

Returns an iterator extracted from the supplied object.

There are four cases, each of which is handled differently:

  1. If obj is a function, this function assumes it is an iterator and returns it.
  2. If obj is a string, this function returns an iterator over the characters of the string.
  3. If obj is a table with an 'iter' field, this function returns obj:iter().
  4. If obj is a table without an 'iter' field, this function returns an iterator over the values of the table, using ipairs()

So, the loop, for e in iter(a) do ... end, works so long as a is one of the types handled by the above cases.

synonyms: iter.from

iter.groupEq(iterable, equalsFn)

Returns an iterator over lists of adjacent elements that are equal according to the supplied equals function (default uses '==').

Example:

iter.groupEq({1,1,2,2,3,3,3,4,5}) --> {1,1}, {2,2}, {3,3,3}, {4}, {5}

iter.interleave(iter1, iter2)

Returns an iteration which alternates between returning elements from iter1 and iter2.

The iteration halts when either iterator runs out of elements.

example: interleave({'a','b','c'}, {1,2,3}) --> a, 1, b, 2, c, 3

iter.last(iterable)

Returns the last element in the iteration over iterable.

The iterator is exhausted by this call.

iter.loop(iterable [,times])

Returns an iterator which cycles the iterable through times repetitions, or forever, if times is nil.

iter.map(iterable, transform)

Returns an iteration in which each element e, in iterable, is replaced by transform(e).

The mapping is 'lazy', so the transform of an element is not applied until that element is requested by the iteration.

Example:

iter.map({1,2,3,4}, math.sqrt) --> sqrt(1), sqrt(2), sqrt(3), sqrt(4)

mapFilter

iter.mapIter(obj)

Extracts a 2-value iterator from obj.

obj may be:

  1. a function (iter.zip("abc",{123}), in which case obj is returned directly
  2. an object with an 'iter' method, in which case obj:iter() is returned
  3. a Lua table {a=1, b=2, c=3}, in which case an iteration over the key-value pairs of the table is returned.

iter.mapN(n, transform)

Returns the result of iter.map(iter.count(n), transform).

Example:

iter.mapN(5, function(x) return x*x end) --> 1, 4, 9, 16, 25

iter.multiEquals(iter1, iter2)

Compares two iterators that return multiple values for equality. The two iterators are equal if both halt after the same number of steps and if, for each iteration step, both return the same values in the same order.

noCycle

openFilter

iter.pack(iterable)

Returns an iterator which packs the result(s) of each iteration step of iter(iterable) into a table.

Example:

iter.pack(iter.mapIter{a=1,b=2,c=3}) will yield {a,1}, {b,2}, {c,3}

pairs

iter.pairsToString(iterable)

Returns a comma-delimted string of the key-value pairs in iterable; each pair of items (a,b) returned by iterable will be denoted by a=b in the returned string.

Example:

> print(iter.pairsToString(iter.zip("abc",{1,2,3})))
a=1, b=2, c=3

pipe

pipeIter

preorder

iter.repeatCall(n, fn, ...)

Returns an iterator which calls the function fn n times with the arguments (...).

Example:

> -- generate a vector of random ints, all in [1..5]
> print( vector(iter.repeatCall(10, math.random, 1, 5)) )
[3, 3, 1, 3, 5, 3, 4, 1, 4, 3]

restartable

resume

iter.reverse(iterable)

Returns an iterator that yields elements in the reverse order of iterable.

This requires allocating a stack to store all the elements in the iteration.

serialize

iter.toList(iterable [, collector])

Converts an iterable to a Lua table.

If collector is specified, collector:add(i) is called for each i in iter(iterable) and collector is returned.

iter.toString(iterable [,delimiter])

Returns a comma+space-delimited string of the elements in iterable, or uses the delimiter if one is provided.

Example:

> print(iter.toString(iter.count(3)))
1, 2, 3

transpose

iter.trim(iterable, count)

Returns an iterator which ignores the first count elements of iterable.

iter.unary(element)

Returns an 'iterator' over a single element.

The returned function will, when first called, return the element, and on subsequent calls return nil.

iter.unpack(iterable)

Equivalent to iter.map(iterable, unpack)

iter.windows(iterable, size)

Returns an iteration in which each step returns size elements in a 'moving window' of the iteration.

Example:

> for lead,follow in iter.windows(vector(1,2,3,4,5), 2) do 
>>  print(lead, follow) end
1       2
2       3
3       4
4       5

iter.zip(...)

'Zips' multiple iterations up into one, similar to the built-in python 'zip' function.

When any one of the iterations returns nil, that iteration is removed from the zip and the zip halts. If resumed, the zip then returns elements from the remaining live iterators.

Example:

a,b = count(5), count(10)
  z = zip(a,b)
  for i,j in z do print(i,j) end --> 1,1  2,2  3,3  4,4  5,5
  for i in z do print(i) end  --> 6  7  8  9  10