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

RecentChanges · preferences
edit · history
Last edited November 27, 2007 8:49 am GMT (diff)