{"id":62,"date":"2015-05-16T00:25:04","date_gmt":"2015-05-16T05:25:04","guid":{"rendered":"http:\/\/www.playwithlua.com\/?p=62"},"modified":"2020-05-22T14:04:16","modified_gmt":"2020-05-22T19:04:16","slug":"iterators","status":"publish","type":"post","link":"http:\/\/www.playwithlua.com\/?p=62","title":{"rendered":"Iterators"},"content":{"rendered":"

Lua doesn’t have a lot of control structures. There’s the obvious if<\/code> statement, the while<\/code> loop and repeat<\/code>\/until<\/code> loop, and the for<\/code> loop. Mostly, the for<\/code> gets used to iterate over tables:<\/p>\n\n

t =<\/span> {<\/span>'a'<\/span>,<\/span>'b'<\/span>,<\/span>'c'<\/span>,<\/span>'d'<\/span>,<\/span>'e'<\/span>}<\/span>\n \nfor<\/span> i,<\/span> v in<\/span> ipairs<\/span>(<\/span>t)<\/span> do<\/span>\n  print<\/span>(<\/span>i,<\/span>t)<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
It’s annoying to have to remember to type ipairs<\/code> every time. I’ve forgotten more than once. But, that minor annoyance is a good trade for the benefit of what the for<\/code> statement actually does: generic iteration.
\n<\/p>\n
What’s an iterator?<\/h2>\n
The for<\/code> statement isn’t just used for looping across tables, it loops through any sort of sequence represented by an iterator. An iterator in Lua is any function that conforms to a certain interface, and a lot of problems can be made simpler by writing your own iterators, instead of just using pairs<\/code> and ipairs<\/code>.<\/p>\n
Let’s look at a standard loop:<\/p>\n\n
t =<\/span> {<\/span>a=<\/span>1<\/span>,<\/span> b=<\/span>2<\/span>,<\/span> c=<\/span>3<\/span>,<\/span> d=<\/span>4<\/span>}<\/span>\nfor<\/span> k,<\/span> v in<\/span> pairs<\/span>(<\/span>t)<\/span> do<\/span>\n  print<\/span>(<\/span>k,<\/span> v)<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
This is using the standard library iterator pairs<\/code>. Let’s take a look at what that call to pairs<\/code> actually returns:<\/p>\n\n
pairs<\/span>(<\/span>t)<\/span>\n-- function: 0x418590    table: 0x141b600    nil<\/span><\/pre><\/div><\/div><\/div>\n\n
Not to keep you in suspense, the table it returns is t<\/code> itself, and the function is the builtin function next<\/code>. What next<\/code> does is take a table and a key in the table, and return the “next” key \/ value. It’s guaranteed to go over all the keys, in no particular order:<\/p>\n\n
next<\/span>(<\/span>t,<\/span> nil<\/span>)<\/span>\n-- c    3<\/span>\nnext<\/span>(<\/span>t,<\/span> 'c'<\/span>)<\/span>\n-- b    2<\/span>\nnext<\/span>(<\/span>t,<\/span> 'b'<\/span>)<\/span>\n-- a    1<\/span>\nnext<\/span>(<\/span>t,<\/span> 'a'<\/span>)<\/span>\n-- d    4<\/span>\nnext<\/span>(<\/span>t,<\/span> 'd'<\/span>)<\/span>\n-- nil<\/span><\/pre><\/div><\/div><\/div>\n\n
So let’s write that original for<\/code> loop in a more explicit way:<\/p>\n\n
for<\/span> k,<\/span> v in<\/span> next<\/span>,<\/span> t,<\/span> nil<\/span> do<\/span>\n  print<\/span>(<\/span>k,<\/span> v)<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
Try it, it does the same thing. In fact, if you just want to go over part of the table, you can pass in an initial argument for next<\/code>:<\/p>\n\n
for<\/span> k,<\/span> v in<\/span> next<\/span>,<\/span> t,<\/span> 'b'<\/span> do<\/span>\n  print<\/span>(<\/span>k,<\/span> v)<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
That will print out just the ‘a’ and ‘d’ keys (yours may vary; next<\/code> iterates in an arbitrary order). That’s all the for<\/code> statement does: it takes a function, an “invariant” first argument (the table), and an initial second argument. It calls the function repeatedly, making the second argument of each call be the first return value of the previous call, until the function returns nil<\/code>.<\/p>\n
Making an iterator<\/h2>\n
With that in mind, we can write our own iterators. Here’s one that loops over members of the triangular series:<\/p>\n\n
function<\/span> triangular(<\/span>_,<\/span> n)<\/span>\n    if<\/span> not<\/span> n then<\/span> n =<\/span> 0<\/span> end<\/span>\n    n =<\/span> n +<\/span> 1<\/span>\n    return<\/span> n,<\/span> n *<\/span> (<\/span>n+<\/span>1<\/span>)<\/span> \/<\/span> 2<\/span>\nend<\/span>\n \nfor<\/span> n,<\/span> v in<\/span> triangular do<\/span>\n    print<\/span>(<\/span>v)<\/span>\n    if<\/span> n ==<\/span> 10<\/span> then<\/span> break<\/span> end<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
Since this iterator will never naturally end, we insert a break<\/code> statement after a while.<\/p>\n
Note how easy calling the iterator is compared to writing it, not that writing it is very hard. This is pretty common with iterators; you spend some effort writing one in order to make the rest of the code simpler.<\/p>\n
A more complex example: depth-first traversal<\/h2>\n
So let’s write some iterators that do actually-useful things, like traversing a tree. What we’d like to be able to do is visit every node of a tree, and get the value of that node and the path down to it from the root. For example:<\/p>\n\n
tree =<\/span> {<\/span>a =<\/span> {<\/span>p =<\/span> {<\/span>p =<\/span> {<\/span>l =<\/span> {<\/span>e =<\/span> {<\/span>}<\/span>}<\/span>}<\/span>}<\/span>,<\/span>\n             n =<\/span> {<\/span>t =<\/span> {<\/span>}<\/span>}<\/span>}<\/span>}<\/span>\n \nfor<\/span> n,<\/span> path in<\/span> dft(<\/span>tree)<\/span> do<\/span>\n  print<\/span>(<\/span>n,<\/span> inspect(<\/span>path)<\/span>)<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
(I’m using inspect.lua<\/a> to print the path, a really handy library).<\/p>\n
This iterator is a little different from the other one: it has complex state, rather than just a single number, so we’ll have dft<\/code> just return a function that keeps the state in a closure. You can do that; for<\/code> doesn’t care if your invariant state is nil<\/code>, it’ll still pass it in every time but you can just ignore it. So, here’s the code:<\/p>\n\n
function<\/span> dft(<\/span>tree)<\/span>\n    local<\/span> value_stack =<\/span> {<\/span>}<\/span>\n    local<\/span> node_stack =<\/span> {<\/span>}<\/span>\n \n    return<\/span> function<\/span>(<\/span>)<\/span>\n        -- These represent the current node:<\/span>\n        local<\/span> value,<\/span> node =<\/span> value_stack[<\/span>#<\/span>value_stack]<\/span>,<\/span> node_stack[<\/span>#<\/span>node_stack]<\/span>\n \n        -- Now, to find the next node:<\/span>\n        if<\/span> not<\/span> next<\/span>(<\/span>node_stack)<\/span> then<\/span>\n            -- Node stack empty, push the root node:<\/span>\n            table.insert<\/span>(<\/span>value_stack,<\/span> (<\/span>next<\/span>(<\/span>tree)<\/span>)<\/span>)<\/span>\n            table.insert<\/span>(<\/span>node_stack,<\/span> tree)<\/span>\n \n        elseif<\/span> next<\/span>(<\/span>node[<\/span>value]<\/span>)<\/span> then<\/span>\n            -- Otherwise, if the current node has children, push them on to the stack:<\/span>\n            table.insert<\/span>(<\/span>value_stack,<\/span> (<\/span>next<\/span>(<\/span>node[<\/span>value]<\/span>)<\/span>)<\/span>)<\/span>\n            table.insert<\/span>(<\/span>node_stack,<\/span> node[<\/span>value]<\/span>)<\/span>\n \n        elseif<\/span> next<\/span>(<\/span>node,<\/span> value)<\/span> then<\/span>\n            -- Otherwise, if there's a right sibling, alter the stack to show it:<\/span>\n            value_stack[<\/span>#<\/span>value_stack]<\/span> =<\/span> next<\/span>(<\/span>node,<\/span> value)<\/span>\n \n        else<\/span>\n            -- Otherwise, pop the stack and find the next node of our parent<\/span>\n            while<\/span> true<\/span> do<\/span>\n                table.remove<\/span>(<\/span>node_stack)<\/span>\n                table.remove<\/span>(<\/span>value_stack)<\/span>\n \n                -- Must be the end of the tree:<\/span>\n                if<\/span> not<\/span> next<\/span>(<\/span>node_stack)<\/span> then<\/span> return<\/span> nil<\/span> end<\/span>\n \n                local<\/span> value,<\/span> node =<\/span> value_stack[<\/span>#<\/span>value_stack]<\/span>,<\/span> node_stack[<\/span>#<\/span>node_stack]<\/span>\n                if<\/span> next<\/span>(<\/span>node,<\/span> value)<\/span> then<\/span>\n                    value_stack[<\/span>#<\/span>value_stack]<\/span> =<\/span> next<\/span>(<\/span>node,<\/span> value)<\/span>\n                    break<\/span>\n                end<\/span>\n            end<\/span>\n        end<\/span>\n \n        -- Return the top of the value stack, and the current value stack<\/span>\n        return<\/span> value_stack[<\/span>#<\/span>value_stack]<\/span>,<\/span> value_stack\n    end<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
This is pretty straightforward. We keep a stack of the node labels \/ values we’ve visited, going back up to the root. We start with empty stacks, and find the next node in the traversal:<\/p>\n