Python Lists

wiki

Python

[Python] is a popular language that contains lists and dictionaries. Lua's table is a multipurpose container that is somewhere in between but in itself lacks functionality as a list. The functions table.insert, table.remove and table.getn from the Lua standard library give tables list functionality (or more specifically termed arrays in Lua). The listing below emulates Python's list type. Section 5.1 [1] of the Python Tutorial documents Python's list functionality.

Implementation

We create a class table, List, containing methods. We use Lua's index metamethod to call the List methods (for background info see ClassesAndMethods).

This version has been rewritten for Lua 5.1 (although the original has been kept) with overloads added for the concatenation and equality operators. For slices, the start and finish are now an inclusive range, which is more Lua-ish. There is also a slice_assign method for the Python construct s[i1:i2] = seq.

-- SteveDonovan

Examples

The code below allows you do things like:

lst = List:new()  -- create an empty List
lst2 = List:new{1,2,"blah",lst}  -- create a list with some items in
lst3 = List {10,20,30}  -- List acts like a 'constructor'
-- Our new methods
lst:append("hello")
lst:extend{"world", 35, 77, "?"}
lst:insert(3,"how?")
lst:remove(35)
q = lst:pop()
print( lst:index("world") )
print( lst:count("?") )
lst:sort()
lst:reverse()
print( lst[-2] )
a = lst:slice(3)
b = lst:slice(-4,-2)
lst:clear()
lst:range(77)

-- We can mix them with Lua's library calls
table.insert(lst,"boo")
print(#lst)

This interactive session demonstrates some of the operations. Note that these list objects can be called as if they were functions, which is a shortcut for the slice method.

C:\lang\lua\projects\libs>lua
Lua 5.1.2  Copyright (C) 1994-2007 Lua.org, PUC-Rio
> require 'pylist'
> a = List {10,20,30}
> b = List {1,2,3}
> = a..b
{10,20,30,1,2,3}
> = a:slice(2,3)
{20,30}
> = a[-1]
30
> = a:index(30)
3
> a:append(40)
> = a
{10,20,30,40}
> = List {1,2} == List{1,2}
true
> = List {1,2} == List{1,4}
false
> = a(2,-1)
{20}
> = a(-2)
{20,30}

-- Emulation of Python lists
-- Nick Trout
-- See http://www.python.org/doc/current/tut/tut.html, section 5.1
-- Note:The comments before some of the functions are from the Python docs
-- and contain Python code.
-- Written for Lua version 4.0
-- Redone for Lua 5.1, Steve Donovan.

local tinsert = table.insert
local tremove = table.remove
local tsort = table.sort
local write = io.write

-- metatable for our list objects
List = {}
List.__index = List
-- we give the metatable its own metatable so that we can call it like a function!
_ListMT = {}
setmetatable(List,_ListMT)
function _ListMT.__call(tbl,arg)
  return List:new(arg)
end

-- Handle the index event
-- note: this is called if something is _not_ present in the table. These are either 
-- negative indices, method names, or bad indices.
function List:__index(i)
  local typ = type(i)
  if typ=="string" then
    local fn = List[i]
    if not fn then error("Bad List function: "..i) end
    return fn
  elseif typ=="number" then
    if i<0 then
      local sz = #self
      if i<-sz then error("List index out of range: "..i) end
      return self[sz+i+1]
    else
      error("Bad list index: "..i)
    end
  end
end

-- The newindex event handles list[i] = val, if i is not present in 
-- the list - used for negative indices!
function List:__newindex(i,val)
  if type(i)=="number" then
    if i<0 then
      local sz = #self
      if i<-sz then error("List index out of range: "..i) end
      self[sz+i+1] = val
    else
      error("Bad list index: "..i)
    end
  end
end

local function simple_table(t)
  return type(t) == 'table' and getmetatable(t) ~= List
end

-- Create a new list. Can optionally pass a list eg. x=List:new{1,2,3}
-- passing another instance of List will cause a _copy_ to be created
-- we pass anything which isn't a simple table to iter() to work out
-- an appropriate iterator
function List:new(t)
  if not t then t={} 
  elseif  not simple_table(t) then
    local tbl = t
    t = {}
    for i,v in iter(tbl) do
      tinsert(t,v)
    end
  end
  setmetatable(t,List)
  return t
end

--Add an item to the end of the list; equivalent to a[len(a):] = [x].
function List:append(i)
  tinsert(self,i)
end

-- Extend the list by appending all the items in the given list;
-- equivalent to a[len(a):] = L.
function List:extend(L)
  assert(type(L)=="table","List:extend expecting a table")
  for i,v in ipairs(L) do tinsert(self,v) end
end

-- Insert an item at a given position. The first argument is the index of the
-- element before which to insert, so a.insert(0, x) inserts at the front of
-- the list, and a.insert(len(a), x) is equivalent to a.append(x).
function List:insert(i, x)
  tinsert(self,i,x)
end

-- equivalent of Python's del s[i]
List.delete = tremove

-- Remove the first item from the list whose value is x.
-- It is an error if there is no such item.
function List:remove(x)
  for i=1,#self do
    if self[i]==x then tremove(self,i) return end
  end
  error("List:remove failed, item not found")
end

-- Remove the item at the given position in the list, and return it.
-- If no index is specified, a.pop() returns the last item in the list.
-- The item is also removed from the list.
function List:pop(i)
  if not i then i = #self end
  return tremove(self,i)
end

-- Return the index in the list of the first item whose value is x.
-- It is an error if there is no such item.
function List:index(x)
  for i=1,#self do
    if self[i]==x then return i end
  end
  error("List:index failed, item not found")
end

-- Return the number of times x appears in the list.
function List:count(x)
  local cnt=0
  for i=1,#self do
    if self[i]==x then cnt=cnt+1 end
  end
  return cnt
end

-- Sort the items of the list, in place.
function List:sort()
  tsort(self)
end

-- Reverse the elements of the list, in place.
function List:reverse()
  local t,n={},#self
  for i=1,n do t[i]=self[n-i+1] end -- reverse
  for i=1,n do self[i]=t[i] end -- copy back
end

local function normalize_slice(self,first,last)
  local sz = #self
  if not first then first=1 end
  if first<0 then first=sz+first+1 end
  -- make the range _inclusive_!
  if not last then last=sz end 
  if last < 0 then last=sz+last end
  return first,last
end

-- Emulate the list slice eg. python_list[first:last]
-- If first or last are negative then they are relative to the end of the list
-- eg. slice(-2) gives last 2 entries in a list,
-- eg. slice(-4,-2) gives from -4th to -2nd
function List:slice(first,last)
  first,last = normalize_slice(self,first,last)
  local t=self:new()
  for i=first,last do tinsert(t,self[i]) end
  return t
end

-- empty the list
function List:clear()
  for i=1,#self do tremove(self,i) end
end

-- Emulate Python's range(x) function which gives you a sequence of 0..x-1
-- Include it in List table for tidyness
function List:range(x)
  local t=self
  if type(t) == 'number' then -- we did not get a self argument - it was a number!
    x = t
    t=List:new()    
  end
  for i=0,x-1 do tinsert(t,i) end
  return t
end

-- Python len(list) is the same as #list
function List:len()
  return #self
end

-- Extended operations --

-- equivalent to del s[i1:i2]
function List:chop(i1,i2)
    i1,i2 = normalize_slice(self,i1,i2)
    for i = i1,i2 do
        tremove(self,i1)
    end
end

-- equivalent to s[idx:idx] = seq
function List:splice(idx,seq)
    idx = idx - 1
    for i,v in ipairs(seq) do
        tinsert(self,i+idx,v)
    end
end

-- general slice assignment s[i1:i2] = seq
function List:slice_assign(i1,i2,seq)
    i1,i2 = normalize_slice(self,i1,i2)
    if i2 >= i1 then self:chop(i1,i2) end
    self:splice(i1,seq)
end

-- concatenation operator ..
function List:__concat(L)
  local ls = self:slice(1,-1)  -- making a copy!
  ls:extend(L)
  return ls
end

-- equality operator ==
function List:__eq(L)
--~   print(#self,#L)
  if #self ~= #L then return false end
  for i = 1,#self do
--~     print(self[i],L[i])
    if self[i] ~= L[i] then return false end
  end
  return true
end

-- how our list should be rendered as a string
-- note: really can't handle list items which are not strings or numbers
function List:__tostring()
  return '{'..table.concat(self,',')..'}'
end

-- can use the call notation to extract slices!
function List:__call(first,last)
  return self:slice(first,last)
end

function List:foreach(fun)
  for i,v in ipairs(self) do
    fun(v)
  end
end

-- capturing the Python concept of 'sequence'. 
-- In particular, this makes strings and file objects to be iterable sequences.
function iter(seq)
    if type(seq) == 'string' then
        local idx = 0
        local n = #seq
        local sub = string.sub
        return function ()
            idx = idx + 1
            if idx > n then return nil
            else
                return idx,sub(seq,idx,idx)
            end
        end
    elseif type(seq) == 'table' then
        return ipairs(seq)
    elseif type(seq) == 'function' then
        return seq()
    elseif type(seq) == 'userdata' and io.type(seq) == 'file' then
        local lines = seq:lines()
        local k = 0
        return function ()
            local line = lines()
            if not line then
              return nil 
            else
                k = k + 1
                return k,line
            end
        end			
    end
end

-- test using: lua pylist.lua
if arg and arg[0]=="pylist.lua" then
  local pr = function(l)
    for i=1,#l do io.write(l[i],' ') end
    print()
  end
  local lst = List:new()
  lst:append(10)
  lst:extend{20,30,40,50}
  assert (lst == List{10,20,30,40,50})
  lst:insert(3,11)  
  lst:remove(40)
  assert (lst == List{10,20,11,30,50})
  local q=lst:pop()
  assert( lst:index(30)==4 )
  assert( lst:count(10)==1 )
  lst:sort()
  lst:reverse()
  assert (lst == List{30,20,11,10})
  assert (lst[-1] == 10)
  assert (lst[-3] == 20)
  lst = List {10,20,30,40,50}
  assert (lst:slice(2) == List{20,30,40,50})
  assert (lst:slice(-2) == List{40,50})
  assert (lst:slice(nil,3) == List{10,20,30})
  assert (lst:slice(2,4) == List{20,30,40})
  assert (lst:slice(-4,-2) == List{20,30})
  lst = List.range(10)
  seq = List{0,1,2,3,4,5,6,7,8,9}
  assert(lst == seq)
  assert (List('abcd') == List{'a','b','c','d'})
  ls = List{10,20,30,40}
  ls:slice_assign(2,3,{21,31})
  assert (ls == List{10,21,31,40})
end

Older Example for Lua 4.0

The code below allows you do things like:

lst = List:new()  -- create an empty List
lst2 = List:new{1,2,"blah",lst}  -- create a list with some items in

-- Our new methods
lst:append("hello")
lst:extend{"world", 35, 77, "?"}
lst:insert(3,"how?")
lst:remove(35)
q = lst:pop()
print( lst:index("world") )
print( lst:count("?") )
lst:sort()
lst:reverse()
print( lst[-2] )
a = lst:slice(3)
b = lst:slice(-4,-2)
lst:clear()
lst:range(77)

-- We can mix them with Luas syntax
tinsert(lst,"boo")
print(getn(lst))

-- Emulation of Python lists
-- Nick Trout
-- See http://www.python.org/doc/current/tut/tut.html, section 5.1
-- Note:The comments before some of the functions are from the Python docs
-- and contain Python code.
-- Written for Lua version 4.0

List = settag({},newtag())

-- Handle the tagmethod "index"
function List:_index(i)
  local typ = type(i)
  if typ=="string" then
    local fn = List[i]
    if not fn then error("Bad List function: "..i) end
    return fn
  elseif typ=="number" then
    if i<0 then
      local sz = getn(self)
      if i<-sz then error("List index out of range: "..i) end
      return self[sz+i+1]
    else
      error("Bad list index: "..i)
    end
  end
end

settagmethod(tag(List), "index", List._index)

-- Create a new list. Can optionally pass a list eg. x=List:new{1,2,3}
function List:new(t)
  if not t then t={} end
  settag(t,tag(List))
  return t
end

--Add an item to the end of the list; equivalent to a[len(a):] = [x].
function List:append(i)
  tinsert(self,i)
end

-- Extend the list by appending all the items in the given list;
-- equivalent to a[len(a):] = L.
function List:extend(L)
  assert(type(L)=="table","List:extend expecting a table")
  for i=1,getn(L) do tinsert(self,L[i]) end
end

-- Insert an item at a given position. The first argument is the index of the
-- element before which to insert, so a.insert(0, x) inserts at the front of
-- the list, and a.insert(len(a), x) is equivalent to a.append(x).
function List:insert(i, x)
  tinsert(self,i,x)
end

-- Remove the first item from the list whose value is x.
-- It is an error if there is no such item.
function List:remove(x)
  for i=1,getn(self) do
    if self[i]==x then tremove(self,i) return end
  end
  error("List:remove failed, item not found")
end

-- Remove the item at the given position in the list, and return it.
-- If no index is specified, a.pop() returns the last item in the list.
-- The item is also removed from the list.
function List:pop(i)
  local item=i
  if not item then item=getn(self) end
  return tremove(self)
end

-- Return the index in the list of the first item whose value is x.
-- It is an error if there is no such item.
function List:index(x)
  for i=1,getn(self) do
    if self[i]==x then return i end
  end
  error("List:index failed, item not found")
end

-- Return the number of times x appears in the list.
function List:count(x)
  local cnt=0
  for i=1,getn(self) do if self[i]==x then cnt=cnt+1 end end
  return cnt
end

-- Sort the items of the list, in place.
function List:sort()
  sort(self)
end

-- Reverse the elements of the list, in place.
function List:reverse()
  local t,n={},getn(self)
  for i=1,n do t[i]=self[n-i+1] end -- reverse
  for i=1,n do self[i]=t[i] end -- copy back
end

-- Emulate the list slice eg. python_list[first:last]
-- If first or last are negative then they are relative to the end of the list
-- eg. slice(-2) gives last 2 entries in a list,
-- eg. slice(-4,-2) gives from -4th to -2nd
function List:slice(first,last)
  local sz = getn(self)
  if not first then first=1 end
  if first<0 then first=sz+first+1 end
  if not last then last=sz else last=last-1 end
  if last<0 then last=sz+last+1 end
  local t=self:new()
  for i=first,last do tinsert(t,self[i]) end
  return t
end

-- empty the list
function List:clear()
  for i=1,getn(self) do tremove(self,i) end
end

-- Emulate Pythons range(x) function which gives you a sequence of 0..x-1
-- Include it in List table for tidyness
function List:range(x)
  local t=self
  if not t then t=List:new() end
  for i=0,x-1 do tinsert(t,i) end
  return t
end

-- Python len(list) is the same as getn
List.len = getn

-- test using: lua -f pylist.lua -test
if arg and arg[1]=="-test" then
  local pr = function(l) for i=1,getn(l) do write(l[i]) end print() end
  local lst = List:new()
  lst:append("hello ") pr(lst)
  lst:extend{"world ","are ","you ","diddling ","?"} pr(lst)
  lst:insert(3,"how ") pr(lst)
  lst:remove("diddling ") pr(lst)
  local q=lst:pop() pr(lst)
  assert( lst:index("are ")==4 )
  assert( lst:count("are ")==1 )
  lst:sort() pr(lst)
  lst:reverse() pr(lst)
  tinsert(lst,"boo") pr(lst)
  print( getn(lst), lst:len(), List.len(lst) )
  print( lst[1],lst[-1],lst[-3] )
  --print( lst[0] )  -- test errors
  --print( lst[100] )
  --print( lst[-100] )
  write("list: ") pr(lst)
  write("[2:] : ")  pr( lst:slice(2) )
  write("[-2:] : ")  pr( lst:slice(-2) )
  write("[:3] : ")  pr( lst:slice(nil,3) )
  write("[:-2] : ") pr( lst:slice(nil,-2) )
  write("[2:4] : ") pr( lst:slice(2,4) )
  write("[-4:-2] : ") pr( lst:slice(-4,-2) )
  lst:clear() pr(lst)
  pr( List:range(10) )
  lst:range(20) pr(lst)
end

--NickTrout

Lists by comprehension in MetaLua

Another handy feature of python lists, which can also be found in Haskell[2], is the specification of lists by comprehension: generating lists through cartesian products and filtering is made easier and more readable. Metalua comes with a sketchy implementation of this features, plus a couple of others idioms such as list sampling:

-{extension "clist"}
-- integers from 2 to 50, by steps of 2:
x = { i for i = 2, 50, 2 }

-- the same, obtained by filtering over all integers <= 50:
y = { i for i = 1, 50 if i%2==0 }

-- prime numbers, implemented in an inefficient way:
local sieve, n = { i for i=2, 100 }, 1
while n < #sieve do
   sieve = { 
      i for i in values(sieve[1 ... n]);
      i for i in values(sieve[n+1 ... #sieve]) if i%sieve[n] ~= 0 }
   n += 1
end
table.print(sieve)

-- FabienFleutot

An alternative implementation of this syntax (without the filter clause) can be found in LuaMacros -- SteveDonovan

A question of Lua Style

There are several functions like List.index which throw an error, rather than returning false. This is appropriate Python style, but more awkward in Lua because the built-in exception handling mechanism is more clumsy. So should these methods return a boolean, rather? We can depend on nil not being a valid value, unlike in Python.

-- SteveDonovan