how to represent nil in a table

Question

Let's suppose I want to store a list of element. Including some nil values. The position of the values is significant, and I need to represent the absence of a value in the list at a given position.

Here is a problem:

a = {1,2,3,nil,4}

for k,v in ipairs(a) do
  print(k,v)
end

print(a[4]) 
print(a[5])

The for loop will only print elements 1,2 and 3. It stops at nil. The first print statement prints nil, but I'm not sure if it is actually stored in the table or not. (Who knows?) The second print statement prints 4 - as expected.

So here is the question: how to represent a list of elements in a table, and iterate through them efficiently? Given the conditions above, e.g. the position is significant, and some of the positions are "empty". In other words: have no value, but the absence of that value at that position has a meaning.

Exteroceptor

Answer 1

This is module "null.lua"

local function null(...)
   local t, n = {...}, select('#', ...)
   for k = 1, n do
      local v = t[k]
      if     v == null then t[k] = nil
      elseif v == nil  then t[k] = null
      end
   end
   return (table.unpack or unpack)(t, 1, n)
end
_G.null = null

Use null() as encoder and decoder

require("null")

a = {null(1,2,3,nil,4)}
-- the same could be done element-by-element
-- a = {null(1),null(2),null(3),null(nil),null(4)}

for k,v in ipairs(a) do
   v = null(v)
   print(k,v)
end

print(null(a[4]))
print(null(a[5]))

Copartner

I'm accepting this answer because it uses a native table and the native ipairs, very straightforward to use, and also handles truth value testing nicely. – Exteroceptor

Answer 2

Lua tables can be used to create any Abstract Data Structure, in your case you indicated that you want a "list". A Lua table is a data structure that combines numeric index based access with key:value access.

Based on your example, you are using the numeric index feature of tables that let you iterate (with ipairs()) through those values. You will not be able to put nil into the table since the numeric index stops at the first nil entry. The remaining values in the table are stored as key:value pairs.

There are several work-arounds, but it depends on why you want a nil in the list. The simplest approach is to use the string "nil" rather than the native data type nil.

a = {1, 2, 3, "nil", 4}

for k,v in ipairs(a) do
  print(k,v)
end

The result of this code is:

1   1 
2   2
3   3
4   nil
5   4

Because of the way Lua implements strings, there is not a performance penalty for comparing to the string "nil" versus comparing to the native type nil.

The issue of "holes" (caused by nil) in an array are discussed in Programming in Lua, Chapter 5 Tables. Roberto Ierusalimschy recommendation is to track the size of the array to avoid problems with holes.

The following code shows an Object Oriented approach to tracking the size of the list. There are many possible variations on this theme.

function makeList(...)
  local list = table.pack(...)

  list.length = 
    function(self) return self.n 
    end

  list.append = 
    function(self, value)
      self.n = self.n + 1
      self[self.n] = value
    end

  list.print = 
    function(self)
      for i = 1, self.n do print(i, self[i]) end
    end

  return list
end

a = makeList(1, 2, 3, nil, 4)
a:append(5)

a:print()

print(a:length())

The result is:

1   1
2   2
3   3
4   nil
5   4
6   5
6

Note that the function table.pack creates a field 'n' which contains the correct number of items even when 'nil' is present. See PIL chapter 6.2, Variadic Functions for a complete explanation.

Killigrew

The usual idiom for this is to define null={} once and use null instead of nil. – Yolandayolande

Okay, this is a workaround. I understand that I can use null or "nil" instead of nil. But I see this as a shortcoming of Lua. For example, what if I also need to test the truth value of the elements? What if the elements are returned by function calls. Then I have to refactor the code and add boilerplate code. That is not an efficient way to do it. – Exteroceptor

I guess I should accept this answer. I can come up with a workaround that uses two tables (one for keys and one for values). That structure could use nil values natively. But that is not an easy and efficient way to do it. But it seems there is no native solution, only workarounds. – Exteroceptor

No offense, but i think this approach is terrible. By using "nil" (a string), debugging gets really really terrible. – Polished

There is also a port of the standard table library that uses a .n-field instead of the length operator # for determining the array length. This way nil values are not any different. – Ammann

2nd paragraph is almost entirely incorrect or implementation-specific. It is ipairs that stops iterating as documented. The table constructor creates integer keys for all the non-nil values also as documented. – Deceit

Is there also a way to add null without parenthesis? – Priggery

Answer 3

Well, you can't store nil in the table without issues.

The most simple solution here would be to introduce your own unique value.

local mynil = {} -- every new table is unique!

a = {1,2,3,mynil,4}

for k,v in ipairs(a) do
  if (v == mynil) then
    v = nil
  end
  print(k,v)
end

No more issues with "nil" string that might be stored in the table as well, the minor issue is one more comparison. ipairs or any other iterator will show that the key with mynil value exists. That means you can separate mynil key existence with missing key =nil.

P.S. If you want to shift your list, you may consider table.remove(list, key) function.

Nicotine

Answer 4

Don't just hack something together, write your own datastructure for this. If you "overload" ipairs (by writing an appropriate iterator) you can use it as a table:

function create(...)
    local t = table.pack(...)
    local self = {
        num = t.n,
        elements = { ... }
    }
    return self
end

function elements(t)
    local f = function(s, i)
        i = i + 1
        if i <= s.num then
            return i, s.elements[i]
        end
    end
    return f, t, 0
end

local seq = create(1, 2, nil, 3)

print(seq.num)
for i, e in elements(seq) do
    print(i, e)
end
-- results:
-- 4
-- 1    1
-- 2    2
-- 3    nil
-- 4    3

You could know define a metatable for this structure and have it use its own ipairs, so you don't even have to change the name.

Polished

Answer 5

The answer to this is rather simple, and these "workaround a" suggested is definitely overkill. Just keep track of the number of items in your table whenever it's changed (note: do not use #, you have too keep track manually to deal with nil values) and use a numeric for loop to iterate over it.

Phlegmy

I don't think a clever solution for this is "overkill". I would always prefer writing ~20 lines than having to think about using the structure every time is use it. – Polished