Range Over Iterators in Lua

Iterating over Custom Data Structures and Infinite Sequences in Lua#

Starting with version 1.23, Lua has table functions that allow us to iterate over any table using pairs and ipairs. Let’s explore how to implement iterators in Lua for a custom data structure and infinite sequences.

Consider a List type, which is a linked list in Lua. We will add elements to the list and iterate over them using an iterator function.

List = {}
List.__index = List

function List:new()
    local self = setmetatable({}, List)
    self.head = nil
    self.tail = nil
    return self
end

Node = {}
Node.__index = Node

function Node:new(value, next)
    local self = setmetatable({}, Node)
    self.value = value
    self.next = next
    return self
end

function List:push(value)
    local newNode = Node:new(value, nil)
    if not self.tail then
        self.head = newNode
        self.tail = newNode
    else
        self.tail.next = newNode
        self.tail = newNode
    end
end

function List:all()
    local function iterator(list, node)
        if node == nil then
            return list head
        else
            return node.next
        end
    end
    return iterator, self, nil
end

-- Create a new list and push values to it
local lst = List:new()
lst:push(10)
lst:push(13)
lst:push(23)

-- Iterate over all elements in the list using the custom iterator
for node in lst:all() do
    print(node.value)
end

-- Collecting all values into a table
local all = {}
for node in lst:all() do
    table.insert(all, node.value)
end
print("all: ", table.concat(all, ", "))

-- Infinite Fibonacci Sequence
function genFib()
    local a, b = 1, 1
-- The infinite iterator function
    return function ()
        local value = a
        a, b = b, a + b
        return value
    end
end

-- Iterate over Fibonacci numbers until breaking condition
for n in genFib() do
    if n >= 10 then break end
    print(n)
end

Explanation#

Let’s break down the Lua code:

1. List and Node Definitions:

   • We define a List table structure that can hold our linked list. Each List has a head and a tail.
   • The Node table structure holds individual elements, each containing a value and a next pointer.

2. Push Method:

   • The push method adds a new node to the list. If the list is empty, it initializes the head and tail. Otherwise, it appends to the tail.

3. Iterator for All Elements:

   • The all method returns an iterator function. This function is used to iterate over all elements in the list.
   • The iterator function returns the next node each time it is called, starting from the head.

4. Usage:

   • We create a list, add some elements using the push method, and then iterate over them using for node in lst:all() do.
   • We also collect all elements into a Lua table using table.insert and print them using table.concat.

5. Infinite Fibonacci:

   • The genFib function returns an infinite iterator for Fibonacci numbers.
   • The iteration proceeds indefinitely until a break condition is met (if n >= 10 then break).

This approach to iterators in Lua allows for clean and idiomatic iteration over both finite and potentially infinite sequences.