Lua: is_array()

The Lua standard libraries provide nothing for determining if a given table is an array. In this post I want to present an elegant implementation of an is_array() function devised by members of the LÖVE community and to discuss both why it works and how it avoids the pitfalls of other approaches.

Credit

These ideas for is_array() came from this thread, particularly from Kikito, Wojak, and Roland Yonaba. They deserve credit for this.

The Implementation

We will begin with the is_array() code itself, and then break it down:

function is_array(t)
    local i = 0
    for _ in pairs(t) do
        i = i + 1
        if t[i] == nil then return false end
    end
    return true
end

(Update: 3 March 2014) An alternative implementation by Pierre Chapuis.

Discussion

The first thing one may wonder is why the function manually keeps a count, i.e. the i variable, instead of using ipairs(). Let us think about what we consider an ‘array’ in Lua. Programmers familiar with the language will know that we use tables to represent arrays. The closest that Lua 5.2 defines as array is what it calls a sequence:

Unless a __len metamethod is given, the length of a table t is only defined if the table is a sequence, that is, the set of its positive numeric keys is equal to {1..n} for some integer n. In that case, n is its length. Note that a table like

{10, 20, nil, 40}

is not a sequence, because it has the key 4 but does not have the key 3. (So, there is no n such that the set {1..n} is equal to the set of positive numeric keys of that table.) Note, however, that non-numeric keys do not interfere with whether a table is a sequence.

The last sentence is key to why we do not use ipairs() in the implementation. It would only iterate over numeric keys. But Lua says that the existence of non-numeric keys does not disqualify a table from being a sequence, i.e. an array for our purposes. So we use pairs() instead to search through all keys. We want to know if there are any ‘nil holes’ even between non-numeric keys.

With this in mind we could write this simple implementation:

function is_array(t)
    local count = 0
    for _,_ in pairs(t) do count = count + 1 end
    return count == #t
end

(Note: Using the variable name _ is great for variables you do not care about during loops.)

This function builds a number of all of the keys in t and then compares it with #t, i.e. it uses the length operator. Therein lies a problem.

Be Wary the Length Operator

From the manual quote above:

Unless a __len metamethod is given, the length of a table t is only defined if the table is a sequence…

In other words, if the table has nil keys then the official language description says that the result of #t is undefined. I tested out the use of #t on various Lua implementations. They produced the same answers but that still does not address the issue that #t for a t that contains nil holes is undefined. And therefore it is unrealiable.

Find Holes in the Original

Here is the implementation again so that you don’t have to bother scrolling up. Notice the check for nil to find such holes to determine if a table is not a ‘sequence’ in Lua terms.

function is_array(t)
    local i = 0
    for _ in pairs(t) do
        i = i + 1
        if t[i] == nil then return false end
    end
    return true
end

The loop within looks ahead to the next element to see if it has a nil value. Unlike Python this will not raise a KeyError exception or anything similar if t[i + 1] happens to reference an element that does not exist.

I have not yet tested it but I believe this is_array() would work well with tables that implement __pairs and other such metamethods. In that case it would be useful to see if such a table is ‘array-like’ enough, for some definition of ‘array-like’ that would probably vary between projects.

Conclusion

A quite useful function overall, with an elegant implementation. Again I suggest reading the original thread to see the incremental development of the function. It dives into some more details about the design which I have not mentioned here.

A great tool that is going right into my Lua file of commonly-used utility functions.

Advertisements

Add Your Thoughts

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s