1   Introduction

This article describes and provides a few implementations of Lua iterators. These iterators are roughly similar in functionality to a few of the tools in the "Lua Functional" library. See -- https://luafun.github.io/

Motivation -- My goal is not just to make available a few usable tools, but also to provide sample code that can be copied and modified to produce custom iterators of your own.

2   Other approaches

You should note that the implementations given below are not the only way to implement Lua iterators. You may also want to consider the following approaches:

2.1   Coroutines as iterators

With this strategy, we implement producer/consumer pairs of functions as Lua coroutines. For a explanation, see -- https://www.lua.org/pil/9.2.html Imagine a chain of Lua coroutines. Each coroutine in the chain is a producer for the next coroutine in the chain, which "consumes" the items that the previous coroutine produces (with coroutine.yield), one by one, by "resuming" (coroutine.resume) that producer coroutine. And, then the consumer, in turn, is or can be a producer for the next coroutine in the chain.

Here is a simple example:

function file_producer(filename)
  local status = 'normal'
  local infile = io.open(filename, 'r')
  while true do
    if status == 'closed' then
      coroutine.yield(nil)
    else
      line = infile:read('l')
      if line == nil then
        infile:close()
        status = 'closed'
      end
      coroutine.yield(line)
    end
  end
end

function file_to_upper(filename)
  print('filename:', filename)
  local flag, line, line2
  local co = coroutine.create(file_producer)
  while true do
    flag, line = coroutine.resume(co, filename)
    if line == nil then
      coroutine.yield(nil)
    else
      line2 = string.upper(line)
      coroutine.yield(line2)
    end
  end
end

Notes:

  • Function file_producer implements a Lua coroutine. Each time it is "resumed", it produces another line from the specified file.
  • Function file_to_upper is also a Lua coroutine. Each time it is "resumed", it resumes coroutine file_producer to get another line, converts that line to uppercase, and yields (produces) it.
  • Notice that there is a similar structure to these two coroutines. Each has (1) a bit of initialization at the start, followed by (2) a loop. Each time the loop is repeated, it produces ("yields") one item.

And, here is a example of its use:

>  comod = require('coroutines')
>  co = coroutine.create(comod.file_to_upper)
>  coroutine.resume(co, 'test.txt')
_[164] = true
_[165] = "AAA"
>  coroutine.resume(co, 'test.txt')
_[166] = true
_[167] = "BBB"
>  coroutine.resume(co, 'test.txt')
_[168] = true
_[169] = "CCC"
>  coroutine.resume(co, 'test.txt')
_[170] = true
_[171] = "DDD"
>  coroutine.resume(co, 'test.txt')
_[172] = true
_[173] = nil

Here is the contents of the input data file:

aaa
bbb
ccc
ddd

And, without the clutter and output, you can do this:

comod = require('coroutines')
co = coroutine.create(comod.file_to_upper)
coroutine.resume(co, 'test.txt')
coroutine.resume(co, 'test.txt')
coroutine.resume(co, 'test.txt')
coroutine.resume(co, 'test.txt')
coroutine.resume(co, 'test.txt')

The following is an example of using the above iterator/coroutines to accumulate a result, in this case, a table containing the items produced by the iterator/coroutine:

function accum_lengths(filename)
  local flag, line
  local accum_tbl = {}
  local co = coroutine.create(M.file_to_upper)
  while true do
    flag, line = coroutine.resume(co, filename)
    if line == nil then
      return accum_tbl
    end
    table.insert(accum_tbl, {line, string.len(line), utf8.len(line)})
  end
end

function show_codepoints(str, indent)
  for idx, val in ipairs({utf8.codepoint(str, 1, #str)}) do
    print(string.format(
      '%s%d.  char: "%s"  codepoint: %04d',
      indent, idx, utf8.char(val), val
      ))
  end
end

function test01(filename)
  print('test 12')
  local indent = '    '
  local accum = accum_lengths(filename)
  for k, v in ipairs(accum) do
    print(string.format('%d. line: "%s"  length: %s  utf8 length: %s', k, v[1], v[2], v[3]))
    M.show_codepoints(v[1], indent)
  end
end

Notes:

  • Function accum_lengths collects the items produced (yielded) by the iterator and inserts them in a table. When the items have been exhausted, it returns that table.
  • Then it displays information about each of the items in that table.

3   Some sample implementations

You can find the source code for these sample implementations of Lua iterators here -- lua_iterator_examples.zip

3.1   Cycle

Repeat an iterator over and over. See -- https://luafun.github.io/compositions.html#fun.cycle

Consider using this with take (https://luafun.github.io/slicing.html#fun.take) or take_n (https://luafun.github.io/slicing.html#fun.take_n) or take_while or some other mechanism to stop iteration.

#!/usr/bin/env lua

Usage = [[

synopsis:
  Run a cycle iterator.
usage:
  lua test16.lua <limit>
]]

local M = {}

Data = {2, 5, 3, 4}

local function make_cycle_iter(data)  -- [1]
  -- carry mutable data in closure.
  local pos = 0
  local count = 0
  local sum = 0
  local sumofsquares = 0
  local function iter(data, pos)
    pos = pos + 1
    if pos > #data then
      pos = 1
    end
    int_item = tonumber(data[pos])
    count = count + 1
    sum = sum + int_item
    sumofsquares = sumofsquares + (int_item * int_item)
    return pos, int_item, count, sum, sumofsquares
  end
  return iter, data, pos
end

function M.test(limit)
  limit = limit or 10
  local idx = 0
  for pos, item, count, sum, sumofsquares in make_cycle_iter(Data) do
    print(idx, pos, item, count, sum, sumofsquares)
    idx = idx + 1
    if idx >= limit then
      break
    end
  end
end

function test()
  if #arg ~= 1 then
    print(Usage)
    os.exit()
  end
  arg1 = tonumber(arg[1])
  M.test(arg1)
end

--test()
return M

3.2   Drop-while

After skipping a sequence of items that satisfy a predicate, iterate over the remaining elements. See -- https://luafun.github.io/slicing.html#fun.drop_while

#!/usr/bin/env lua

Usage = [[

synopsis:
  Run a dropwhile iterator.
  Iterate over a table of integers.
  Drop (ignore) integers until a predicate fails, then process
    all the remaining integers.
  For each item that is processed
    print the iteger, the accumulated sum of integers, and
    the accumulated sum of squares of integers.
  The iterator function passes state to next iteration in an
    argument (a table), It does not use a closure.

  A simple test:
      >
      > iter = require 'Iterators.drop_while'
      > iter.run({3, 6, 9, 2, 4, 5, 7})
      pos     count   item    sum     sos
      4       1       2       2       4
      5       2       4       6       20
      6       3       5       11      45
      7       4       7       18      94
      >

  Funcion `make_dropwhile_iter` takes a predicate function and an integer
    array as arguments.  It returns an iterator function and a state (table).
    The iterator function can be called as follows:
        iterator_fn(state_tbl)
    Example:
        >
        > iter = require 'Iterators.drop_while'
        > iter_fn, state_tbl = iter.make_dropwhile_iter(p1, {4, 8, 3, 6})
        > iter_fn(state_tbl)
        3       1       3       3       9
        > iter_fn(state_tbl)
        4       2       6       9       45
        > iter_fn(state_tbl)
        nil
        >
    The state can be reset and reused by setting various attributes in it.  E.g.
        >
        > state_tbl.pos = 0
        > state_tbl.sum = 0
        > state_tbl.searching = true
        > iter_fn(state_tbl)
        3       7       3       3       179
        > iter_fn(state_tbl)
        4       8       6       9       215
        > iter_fn(state_tbl)
        nil
        >

command line usage:
  $ LUACLI=1 lua filter_false.lua <integer1> <integer1> ...

example:
  $ LUACLI=1 ./filter_false.lua 44 66 77 99 88 22
]]

local M = {}

Data = {2, 5, 3, 4}

function M.make_dropwhile_iter(predicate, data)
  data = data or Data
  local state_tbl = {
    pos = 0,
    count = 0,
    sum = 0,
    sumofsquares = 0,
    predicate = predicate,
    data = data,
    searching = true
  }
  local function iter(state)
    local int_item
    state.pos = state.pos + 1
    if state.searching then
      while true do
        if state.pos > #state.data then
          return nil
        end
        int_item = tonumber(state.data[state.pos])
        if state.predicate(int_item) then
          --print('yes', int_item)
          state.pos = state.pos + 1
        else
          --print('no', int_item)
          state.searching = false
          break
        end
      end
    end
    if state.pos > #state.data then
      return nil
    end
    int_item = tonumber(state.data[state.pos])
    state.count = state.count + 1
    state.sum = state.sum + int_item
    state.sumofsquares = state.sumofsquares + (int_item * int_item)
    return state.pos, state.count, int_item, state.sum, state.sumofsquares
  end
  return iter, state_tbl
end

function M.predicate01(item)
  return item % 3 == 0
end

function M.test(predicate, data)
  print('pos', 'count', 'item', 'sum', 'sos')
  for pos, count, item, sum, sumofsquares in M.make_dropwhile_iter(predicate, data) do
    print(pos, count, item, sum, sumofsquares)
  end
end

function M.run(args)
  if #args == 1 and (args[1] == '-h' or args[1] == '--help') then
    print(Usage)
    os.exit()
  elseif #args < 1 then
    data = nil
  else
    data = {}
    for _key, value in ipairs(args) do table.insert(data, tonumber(value)) end
  end
  M.test(M.predicate01, data)
end

if os.getenv('LUACLI') ~= nil then
  M.run(arg)
else
  return M
end

3.3   Filter-false

Iterate over a sequence filtering out (skipping) those items that do not satisfy a precicate.

#!/usr/bin/env lua

Usage = [[

synopsis:
  Run a filterfalse iterator.
  Iterate over a table of integers.
  For each item that satisfies the predicate,
    print the iteger, the accumulated sum of integers, and
    the accumulated sum of squares of integers.
  Passes state to each iteration in an argument (a table),
  Does not use a closure.

  A simple test:
            >
            > iter = require 'Iterators.filter_false'
            > iter.run({11, 22, 33, 44, 55})
            no      11
            yes     22
            2       1       22      22      484
            no      33
            yes     44
            4       2       44      66      2420
            no      55
            >

  Funcion `make_filterfalse_iter` takes a predicate function and an integer
    array as arguments.  It returns an iterator function and a state (table).
    The iterator function can be called as follows:
        iterator_fn(state_tbl)
    Example:
        >
        > iter_fn, state_tbl = iter.make_filterfalse_iter(iter.predicate01, {144,133, 155, 144, 166, 155})
        > iter_fn(state_tbl)
        yes     144
        1       1       144     144     20736
        > iter_fn(state_tbl)
        no      133
        no      155
        yes     144
        4       2       144     288     41472
        >
    The state can be reset and reused by setting various attributes in it.  E.g.
        state_tbl['pos'] = 0
        state_tbl['sum'] = 0

command line usage:
  $ lua filter_false.lua <int1> <int1> ...

example:
  $ LUACLI=1 ./filter_false.lua 44 66 77 99 88 22
]]

local M = {}

Data = {2, 5, 3, 4}

function M.make_filterfalse_iter(predicate, data)
  data = data or Data
  local state_tbl = {
    pos = 0,
    count = 0,
    sum = 0,
    sumofsquares = 0,
    predicate = predicate,
    data = data
  }
  local function iter(state)
    local int_item = tonumber(state.data[state.pos])
    while true do
      state.pos = state.pos + 1
      if state.pos > #state.data then
        return nil
      end
      int_item = tonumber(state.data[state.pos])
      if state.predicate(int_item) then
        print('yes', int_item)
        break
      else
        print('no', int_item)
      end
    end
    state.count = state.count + 1
    state.sum = state.sum + int_item
    state.sumofsquares = state.sumofsquares + (int_item * int_item)
    return state.pos, state.count, int_item, state.sum, state.sumofsquares
  end
  return iter, state_tbl
end

function M.predicate01(item)
  return item % 2 == 0
end

function M.test(predicate, data)
  limit = limit or 10
  for pos, count, item, sum, sumofsquares in M.make_filterfalse_iter(predicate, data) do
    print(pos, count, item, sum, sumofsquares)
  end
end

function M.run(args)
  if #args == 1 and (args[1] == '-h' or args[1] == '--help') then
    print(Usage)
    os.exit()
  elseif #args < 1 then
    data = nil
  else
    data = {}
    for _key, value in ipairs(args) do table.insert(data, tonumber(value)) end
  end
  M.test(M.predicate01, data)
end

if os.getenv('LUACLI') ~= nil then
  M.run(arg)
else
  return M
end

3.4   Pair-wise

Iterate over a sequence of items. Return (iterate over) successive pairs of consecutive items. See the examples given in the usage/description comments in the code, below.

#!/usr/bin/env lua

Usage = [[

synopsis:
  Run a pairwise iterator.
  Iterate over a table of integers.
  Create an array of arrays (2-tuples) of successive overlapping
    pairs taken from the input.
  The iterator function passes state to next iteration in an
    argument (a table), It does not use a closure.

  A simple test:
      >
      > iter = require 'Iterators.pairwise'
      > iter.run({3, 6, 9, 2, 4, 5, 7})
      pair:   3       6
      pair:   6       9
      pair:   9       2
      pair:   2       4
      pair:   4       5
      pair:   5       7
      >

  Funcion `make_pairwise_iter` takes an integer
    array as its argument.  It returns an iterator function and a state (table).
    The iterator function can be called as follows:
        iterator_fn(state_tbl)
    Example:
                >
                > iter = require 'Iterators.pairwise'
                > iter_fn, state_tbl = iter.make_pairwise_iter({6, 5, 4, 3, 2})
                > iter_fn(state_tbl)
                table: 0x56484217c2f0
                > iter_fn(state_tbl)
                table: 0x56484217c660
                > iter_fn(state_tbl)
                table: 0x56484217c980
                > iter_fn(state_tbl)
                table: 0x56484217ccb0
                > iter_fn(state_tbl)
                nil
                > state_tbl.pairs
                table: 0x56484217c0f0
                > utils.show_table(state_tbl.pairs)
                1. --------------------
                        key: 1  value: 6
                        key: 2  value: 5
                2. --------------------
                        key: 1  value: 5
                        key: 2  value: 4
                3. --------------------
                        key: 1  value: 4
                        key: 2  value: 3
                4. --------------------
                        key: 1  value: 3
                        key: 2  value: 2
                >

    The state can be reset and reused by setting various attributes in it.  E.g.
        >
        > state_tbl.pos = 0
        > state_tbl.pairs = {}
        >
        > iter_fn(state_tbl)
        table: 0x56484217f4a0
        > iter_fn(state_tbl)
        table: 0x56484217f8b0
        > iter_fn(state_tbl)
        table: 0x56484217fc60
        > iter_fn(state_tbl)
        table: 0x56484215eca0
        > iter_fn(state_tbl)
        nil
        > utils.show_table(state_tbl.pairs)
        1. --------------------
            key: 1  value: 6
            key: 2  value: 5
        2. --------------------
            key: 1  value: 5
            key: 2  value: 4
        3. --------------------
            key: 1  value: 4
            key: 2  value: 3
        4. --------------------
            key: 1  value: 3
            key: 2  value: 2
        >

command line usage:
  $ LUACLI=1 lua pairs.lua <integer1> <integer1> ...

example:
  $ LUACLI=1 ./pairs.lua 44 66 77 99 88 22
]]

local M = {}

Data = {2, 5, 3, 4}

function M.make_pairwise_iter(data)
  data = data or Data
  local state_tbl = {
    pos = 0,
    data = data,
    pairs = {},
  }
  local function iter(state)
    local pair
    state.pos = state.pos + 1
    if state.pos > #state.data then
      return nil
    end
    if state.pos < #state.data then
      pair = {state.data[state.pos], state.data[state.pos + 1]}
      table.insert(state.pairs, pair)
      return pair
    else
      return nil
    end
  end
  return iter, state_tbl
end

function M.test(data)
  local iter, state_tbl
  iter, state_tbl = M.make_pairwise_iter(data)
  for pair in iter, state_tbl do
  end
  local pairs = state_tbl.pairs
  for idx, value in ipairs(pairs) do
    print('pair:', value[1], value[2])
  end
end

function M.run(args)
  local data
  if #args == 1 and (args[1] == '-h' or args[1] == '--help') then
    print(Usage)
    os.exit()
  elseif #args < 1 then
    data = nil
  else
    data = {}
    for _key, value in ipairs(args) do table.insert(data, tonumber(value)) end
  end
  M.test(data)
end

if os.getenv('LUACLI') ~= nil then
  M.run(arg)
else
  return M
end

3.5   Partition

Iterate of a sequence returning a sequences of a given size of non-overlapping consecutive items.

#!/usr/bin/env lua

local Usage = [[

synopsis:
  Run a partition iterator.
  Iterate over a table of items.
  Create an array of arrays (n-tuples) of successive non-overlapping
    tuples taken from the input.
  The iterator function passes state to next iteration in an
    argument (a table), It does not use a closure.

  A simple test:
      >
      > iter = require 'Iterators.partition'
      > iter.run({3, 11, 22, 33, 44, 55, 66, 77, 88, 99})
      tuple 1:
              11
              22
              33
      tuple 2:
              44
              55
              66
      tuple 3:
              77
              88
              99
      >

  Funcion `make_partition_iter` takes an integer array and a
    partition/tuple size as its arguments.  It returns an
    iterator function and a state (table).
    The iterator function can be called as follows:
        iterator_fn(state_tbl)
    Example:
        >
        > iter_fn, state_tbl = iter.make_partition_iter({11, 22, 33, 44, 55, 66, 77, 88, 99}, 4)
        > iter_fn(state_tbl)
        table: 0x556973186e80
        > iter_fn(state_tbl)
        table: 0x556973187260
        > iter_fn(state_tbl)
        table: 0x556973199750
        > iter_fn(state_tbl)
        table: 0x556973198da0
        > iter_fn(state_tbl)
        nil
        > state_tbl.tuples
        table: 0x5569731993d0
        > utils.show_table(state_tbl.tuples)
        1. --------------------
            key: 1  value: 11
            key: 2  value: 22
            key: 3  value: 33
            key: 4  value: 44
        2. --------------------
            key: 1  value: 55
            key: 2  value: 66
            key: 3  value: 77
            key: 4  value: 88
        3. --------------------
            key: 1  value: 99
        4. --------------------
        >

    The state can be reset and reused by setting various attributes in it.  E.g.
        >
        > state_tbl.pos = 0
        > state_tbl.tuples = {}
        > state_tbl.tuplesize = 4
        > iter_fn(state_tbl)
        table: 0x55697319cb80
        > iter_fn(state_tbl)
        table: 0x55697319d420
        > iter_fn(state_tbl)
        table: 0x55697319d7c0
        > iter_fn(state_tbl)
        table: 0x55697319db80
        > iter_fn(state_tbl)
        nil
        > utils.show_table(state_tbl.tuples)
        1. --------------------
            key: 1  value: 11
            key: 2  value: 22
            key: 3  value: 33
            key: 4  value: 44
        2. --------------------
            key: 1  value: 55
            key: 2  value: 66
            key: 3  value: 77
            key: 4  value: 88
        3. --------------------
            key: 1  value: 99
        4. --------------------
        >

command line usage:
  $ LUACLI=1 lua partition.lua <tupesize> <item> <item> ...

example:
  $ LUACLI=1 ./partition.lua 4 11 22 33 44 55 66 77 88 99
]]

local M = {}

function M.make_partition_iter(data, tuplesize)
  local state_tbl = {
    pos = 0,
    data = data,
    tuplesize = tuplesize or 2,
    tuples = {},
  }
  local function iter_fn(state)
    if state.pos >= #state.data then
      return nil
    end
    local tuple = {}
    for idx = 1, state.tuplesize do
      table.insert(tuple, state.data[state.pos + idx])
    end
    table.insert(state.tuples, tuple)
    state.pos = state.pos + state.tuplesize
    return tuple
  end
  return iter_fn, state_tbl
end

function M.test(data, tuplesize)
  local iter_fn, state_tbl
  iter_fn, state_tbl = M.make_partition_iter(data, tuplesize)
  for tuple in iter_fn, state_tbl do
    -- no-op
  end
  local tuples = state_tbl.tuples
  for idx, value in ipairs(tuples) do
    print(string.format('tuple %d:', idx))
    for i, v in ipairs(value) do print('', v) end
  end
end

function M.run(args)
  local data
  if (#args == 1 and (args[1] == '-h' or args[1] == '--help')) or
    #args < 1 then
    print(Usage)
    os.exit()
  elseif #args < 2 then
    tuplesize = tonumber(args[1])
    data = nil
  else
    tuplesize = tonumber(args[1])
    data = {}
    for idx = 2, #args do
      table.insert(data, args[idx])
    end
  end
  M.test(data, tuplesize)
end

if os.getenv('LUACLI') ~= nil then
  M.run(arg)
else
  return M
end

Published

Category

lua

Tags

Contact