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:

It is an iterator function, for instance: a = iter.count(10)
It is an object with an 'iter' method: a = Vector:make{1,2,3,4,5}
It is a vanilla Lua table, for example: a = {1,2,3,4,5}
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:

It is an iterator function which returns two values per step: iter.zip("abc",{1,2,3})
It is an object whose 'iter' method returns a function satisfying 1.
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

`make`	Creates an iterable from the supplied function, or simply returns func if it is already a object with an iter method.
`EMPTY`	An empty iteration.
`__call`	Returns an iterator extracted from the supplied object.
`autofolding`	Turn any binary function into a function which operates on a variable number of arguments, by cascading the results.
`buffer`	...
`chain`	Returns an iterator that is the chaining together of each iterable passed as an argument to this function.
`collapseEq`	Returns an iterator in which adjacent duplicate elements are removed.
`count`	Returns an iterator which counts off successive integers in the range [start..stop] with stepsize step.
`cross`	...
`enum`	Decorates another iteration to return the index of each element returned from the decorated iteration.
`equals`	Returns true if both iterations return the same number of elements and each pair of corresponding elements are equal according to equalsFn (default '==').
`everyNth`	...
`exchange`	Swaps the order that multiple values are returned by two-element iterator.
`filter`	Returns an iteration containing only the elements of iterable for which filter returns true.
`find`	Returns the first object, e from iterable for which predicate(e) returns true, or nil if there are no matches.
`first`	Returns the first element of iterable if k is unspecified, or an iterator over the first k elements.
`fold`	Also sometimes called 'reduce' in functional programming contexts.
`foldIter`	Same as fold, except that intermediate values are returned as an iterator.
`__call`	Returns an iterator extracted from the supplied object.
`groupEq`	Returns an iterator over lists of adjacent elements that are equal according to the supplied equals function (default uses '==').
`interleave`	Returns an iteration which alternates between returning elements from iter1 and iter2.
`last`	Returns the last element in the iteration over iterable.
`loop`	Returns an iterator which cycles the iterable through times repetitions, or forever, if times is nil.
`map`	Returns an iteration in which each element e, in iterable, is replaced by transform(e).
`mapFilter`	...
`mapIter`	Extracts a 2-value iterator from obj.
`mapN`	Returns the result of iter.map(iter.count(n), transform).
`multiEquals`	Compares two iterators that return multiple values for equality.
`noCycle`	...
`openFilter`	...
`pack`	Returns an iterator which packs the result(s) of each iteration step of iter(iterable) into a table.
`pairs`	...
`pairsToString`	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.
`pipe`	...
`pipeIter`	...
`preorder`	...
`repeatCall`	Returns an iterator which calls the function fn n times with the arguments (...).
`restartable`	...
`resume`	...
`reverse`	Returns an iterator that yields elements in the reverse order of iterable.
`serialize`	...
`toList`	Converts an iterable to a Lua table.
`toString`	Returns a comma+space-delimited string of the elements in iterable, or uses the delimiter if one is provided.
`transpose`	...
`trim`	Returns an iterator which ignores the first count elements of iterable.
`unary`	Returns an 'iterator' over a single element.
`windows`	Returns 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:

If obj is a function, this function assumes it is an iterator and returns it.
If obj is a string, this function returns an iterator over the characters of the string.
If obj is a table with an 'iter' field, this function returns obj:iter().
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 no parameters are provided, this iteration will return 1,2,3,etc up to infinity and beyond.
If one param p is provided, start defaults to 1 and stop becomes p, and the iteration returned is [1..p],+1. (The notation [a..b],+1 indicates the iteration a, a+1, a+2,..., b.)
If two params p1, p2 are provided, start becomes p1, stop becomes p2, and the iteration returned is [p1..p2],+1.
If three params p1, p2, p3 are provided, the iteration returned is [p1..p2],+p3. (p3 may be negative)

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:

If obj is a function, this function assumes it is an iterator and returns it.
If obj is a string, this function returns an iterator over the characters of the string.
If obj is a table with an 'iter' field, this function returns obj:iter().
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:

a function (iter.zip("abc",{123}), in which case obj is returned directly
an object with an 'iter' method, in which case obj:iter() is returned
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