how to make anydimensional array?

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

how to make anydimensional array?

Pavol Severa
I'd like to ask what is the most "luaic" implementation of polynomials
in n variables

I was naturally thinking of a table t, with t.dim equal to n, and (say)
t[{k1,k2,..,kn}] equal to the coefficient of the polynomial in front
of (x1^k1 * x2^k2 * .. *xn^kn)
(the 'default value' of the table would not be nil, but rather 0, and
one would implement operations with polynomials using a metatable of
t).

The problem is of course that
t={}
t[ {1,2,3} ]=2
print( t[ {1,2,3} ] )
--> nil

so I tried to overcome {1,2,3}~={1,2,3} with an  __eq field in a metatable:

--------------------------------
meta={}
function meta.__eq(x,y)
   for i,e in ipairs(x) do
     if e~=y[i] then return false
   end
   return true
end

function ind(...)
   local result={...}
   setmetatable(result,meta)
   return result
end
---------------------------------

now ind(1,2,3)==ind(1,2,3)
but to my surprise
t={}
t[ind(1,2,3)]=2
print( t[ ind(1,2,3) ] )
--> nil

So what is a sane solution for this problem? I can imagine rewriting
the function ind so that it returns a string, e.g.
ind(1,2,3)=="1,2,3", and writing a reverse function
rev("1,2,3")==1,2,3. Would that be reasonable? Or should I play with
the metatable of t so that
t[ {1,2,3} ]=2
print( t[ {1,2,3} ] )
-->2
?
(by using the function ind in __index and __newindex? or by other means?)
Or any other solution?
(these are questions from a newbie, of course)

Best regards
P.
Reply | Threaded
Open this post in threaded view
|

Re: how to make anydimensional array?

Paul Chiusano-3
Hi Pavol,

> The problem is of course that
> t={}
> t[ {1,2,3} ]=2
> print( t[ {1,2,3} ] )
> --> nil
>
> so I tried to overcome {1,2,3}~={1,2,3} with an  __eq field in a metatable:
> but to my surprise
> t={}
> t[ind(1,2,3)]=2
> print( t[ ind(1,2,3) ] )
> --> nil

There was a thread about this about a year ago, which you can read
http://lua-users.org/lists/lua-l/2005-06/msg00108.html . I had the
same problem that you are having.

Basically, Lua doesn't currently provide any way for objects to
override how they are hashed when used as keys in a table. So even
though the two {1, 2, 3} tables compare equal according to your
metamethod, the hash is still based on the table's addresses, so the
two tables are never even compared to one another.

There are a couple ways around this issue. One is to "stringify" the
keys, like you mention. This has the problem of requiring that the
keys be perfect string representations of the objects being used as
keys - which means they'll consume just as much memory (or more, since
they are in string form) as the actual objects, in addition to
requiring possibly expensive conversions between string and non-string
forms.

Another approach is to memoize the function which creates the objects
being used as keys such that all equal objects have the same memory
address.  See http://www.lua.org/pil/17.1.html for a discussion of
that. Sometimes works out nicely, other times it doesn't. Suppose
you'd like to use sets as keys for a table. You might build one of
these sets iteratively, adding to it in different parts of your
application. Finally you want to do a lookup of the set you've
created. I think this is a totally reasonable use case, but it's very
difficult to apply memoization in a case like this. (Of course, when
using mutable objects as keys in a table, care must be taken not to
modify the object once it has been inserted as a key.)

The last thing you can do is write your own table variant which checks
for a __hash metamethod (or whatever you'd like to call it) when using
tables as keys. This is what I ended up doing for the collections
framework I wrote:  http://sano.luaforge.net/  (In particular, check
out the documentation for HashMap:
http://sano.luaforge.net/documentation/HashMap.html ).

I'd love to see a future version of Lua have a __hash metamethod, I
really think it's the Right Thing to do. But when I brought this issue
up on the mailing list a year ago, it seemed like there was some
resistance from folks who thought that the above workarounds were
sufficient. I don't know what the Lua author's position is on all of
this.

Hope that helps.

Best,
Paul
Reply | Threaded
Open this post in threaded view
|

Re: how to make anydimensional array?

Luis Carvalho-2
In reply to this post by Pavol Severa
> I'd like to ask what is the most "luaic" implementation of polynomials
> in n variables
>
> I was naturally thinking of a table t, with t.dim equal to n, and (say)
> t[{k1,k2,..,kn}] equal to the coefficient of the polynomial in front
> of (x1^k1 * x2^k2 * .. *xn^kn)
> (the 'default value' of the table would not be nil, but rather 0, and
> one would implement operations with polynomials using a metatable of
> t).

What about:

<poly.lua>
local setmetatable = setmetatable
local type = type
local print = print

module'poly'

local poly_mt = {
  __index = function(o, k) return 0 end,
  __call = function(o, l)
    local e = o
    for i=1,o.dim do e=e[l[i]] end
    return e
  end
}

new = function(dim, degree)
  if dim<=1 then
    return setmetatable({dim=dim, degree=degree}, poly_mt)
  else
    local p = {dim=dim, degree=degree}
    for i=0,degree do p[i] = new(dim-1, degree) end
    return setmetatable(p, poly_mt)
  end
end
</poly.lua>

$ lua
Lua 5.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
> require'poly'
> p = poly.new(3,3)
> p[1][2][3] = 2
> = p[1][2][3]
2
> = p{1,2,3}
2
> = p[1]{2,3}
2
> = p{1,1,0}
0

The hierarchical structure in poly is meant to make it easier to implement
evaluations (Horner's scheme, for example) or operations. Depending on your
needs thaty might not be necessary, that is, you can stick to regular
tables.

Cheers,
luis.

--
A mathematician is a device for turning coffee into theorems.
        -- P. Erdos

--
Luis Carvalho
Applied Math PhD Student - Brown University
PGP Key: E820854A <[hidden email]>