Associative tuples

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

Associative tuples

Gavin Wraith
I was interested to read in http://lua-users.org/wiki/SimpleTuples
about defining pairing functions satisfying the mathematically
necessary condition
  pair (x,x') == pair (y,y') <==> x == y and x' == y'
To recapitulate, we have:

local pair
do -------------------
 local m = function (a) return {
         __index = function (t,b)
                local p = function ( ) return a,b end
                t[b] = p
                return p end }
 local meta = { __index = function (t,a)
                   local v = setmetatable ({ }, m (a))
                   t[a] = v
                   return v end }
 local P = setmetatable ({ }, meta)
 pair = function (x, y) return P[x][y] end
end -----------------

If we then define:

  tuple = function (...)
    local n = select ('#', ...)
    if n < 1 then return end
    if n < 2 then return ... end
    return pair (..., tuple (select (2, ...))) end

we have
   tuple (1,2,3) == tuple (1, tuple (2,3)) --> true
by definition but, alas,
   tuple (1,2,3) == tuple (tuple (1,2), 3) --> false
So are there any associative tupling functions?
<muttering aside>
We probably need to be able to hash not just single items
on the stack but tuples of items, in an associative way. I tried
googling "hashing and tupling" but that particular cast of the
net brought up no relevant research papers as far as I could see.
As a good category theorist I should not be asking for equalities
but for invertible associator functions that satisfy naturality
and MacLane's pentagonal condition; but then monoidal categories
are monoidally equivalent to strict monoidal categories.</muttering>
--
Gavin Wraith ([hidden email])
Home page: http://www.wra1th.plus.com/

Reply | Threaded
Open this post in threaded view
|

Re: Associative tuples

dyngeccetor8
On 01/11/2018 01:09 AM, Gavin Wraith wrote:
> [...]
> we have
>    tuple (1,2,3) == tuple (1, tuple (2,3)) --> true
> by definition but, alas,
>    tuple (1,2,3) == tuple (tuple (1,2), 3) --> false
> So are there any associative tupling functions?
> [...]> --
> Gavin Wraith ([hidden email])
> Home page: http://www.wra1th.plus.com/

Why not implement tuples via lists?

  tuple =
    function(...)
      local result = {type = 'tuple'}

      local process
      process =
        function(list)
          for i, el in ipairs(list) do
            if (type(el) == 'table') and (el.type == 'tuple') then
              process(el)
            else
              table.insert(result, el)
            end
          end
        end

      process({...})

      return result
    end

  is_equal =
    function(t_a, t_b)
      if (#t_a == #t_b) then
        for i = 1, #t_a do
          if (t_a[i] ~= t_b[i]) then
            return false
          end
        end
        return true
      else
        return false
      end
    end


  -- Verification:

  print(
    'true',
    is_equal(
      tuple(1, tuple(2, 3)),
      tuple(tuple(1, 2), 3)
    ),
    is_equal(
      tuple(1, tuple(2, 3)),
      tuple(1, 2, 3)
    ),
    is_equal(
      tuple(1, 2, 3),
      tuple(tuple(1, 2, 3))
    )
  )

  print(
    'false',
    is_equal(
      tuple(1, 2, 3),
      tuple(1, 2)
    ),
    is_equal(
      tuple(1, tuple(2, 3)),
      tuple(1, tuple(2))
    )
  )

-- Martin

Reply | Threaded
Open this post in threaded view
|

Re: Associative tuples

Gavin Wraith
In message <[hidden email]>
          dyngeccetor8 <[hidden email]> wrote:

> Why not implement tuples via lists?
>
>  tuple =
>    function(...)
>      local result = {type = 'tuple'}
>
>      local process
>      process =
>        function(list)
>          for i, el in ipairs(list) do
>            if (type(el) == 'table') and (el.type == 'tuple') then
>              process(el)
>            else
>              table.insert(result, el)
>            end
>          end
>        end
>
>      process({...})
>
>      return result
>    end
>
>  is_equal =
>    function(t_a, t_b)
>      if (#t_a == #t_b) then
>        for i = 1, #t_a do
>          if (t_a[i] ~= t_b[i]) then
>            return false
>          end
>        end
>        return true
>      else
>        return false
>      end
>    end

I was looking for something that worked with ==.  But thanks
anyway.
--
Gavin Wraith ([hidden email])
Home page: http://www.wra1th.plus.com/

Reply | Threaded
Open this post in threaded view
|

Re: Associative tuples

Dirk Laurie-2
2018-01-13 11:59 GMT+02:00 Gavin Wraith <[hidden email]>:

>
>>        end
>>        return true
>>      else
>>        return false
>>      end
>>    end
>
> I was looking for something that worked with ==.  But thanks
> anyway.

If just '==' is good enough, then a metamethod does it.

If you need to use tuples as an index into a table, raw equality
is needed. This can be done in many ways, such as memoizing,
serializing etc, but all the approaches work on the metatable of
the table, not of the tuple.

Reply | Threaded
Open this post in threaded view
|

Re: Associative tuples

Gavin Wraith
In message <CABcj=[hidden email]>
          Dirk Laurie <[hidden email]> wrote:


> If just '==' is good enough, then a metamethod does it.
>
> If you need to use tuples as an index into a table, raw equality
> is needed. This can be done in many ways, such as memoizing,
> serializing etc, but all the approaches work on the metatable of
> the table, not of the tuple.

I was musing in a vague way about the "duality" between functions
f(...), with their fixed space but variable time cost, and tables
f[...] with their fixed time but variable space cost. The symmetry
is broken by the fact that tables do not have multi-indices, but
can be restored by the use of tuples. But tuples are not fully
privileged citizens in Lua (and I am not arguing that they should be),
unlike Haskell. The use of metatables for tables can provide a sort of
dual to the process of memoization, which can be thought of as letting
the programmer trade between space costs and time costs.

--
Gavin Wraith ([hidden email])
Home page: http://www.wra1th.plus.com/