The importance of names

[Reuben Thomas <rrt@...>]

My brain is bubbling gently at the moment after thinking about permuting
lists and tables. It reminds me of a similar experience with merging and
separating lists of lists.

Here are a couple of handy but (to me, and I wrote them!) mysterious
functions:

-- reindex: Change the keys of a table
--   p: list of oldkey=newkey pairs
--   t: table to reindex
-- returns
--   u: reindexed table
function reindex(p, t)
  local u = {}
  for o, n in p do
    u[n] = t[o]
  end
  return t
end

-- transpose: Transpose a list of lists
--   ls: {{l11 .. l1c} .. {lr1 .. lrc}}
-- returns
--   ms: {{l11 .. lr1} .. {l1c .. lrc}}
-- Also give aliases zip and unzip
function transpose(ls)
  local ms, len = {}, getn(ls)
  for i = 1, call(max, map(getn, ls)) do
    ms[i] = {}
    for j = 1, len do
      tinsert(ms[i], ls[j][i])
    end
  end
  return ms
end

Oh yes, I've also used the much less mysterious map:

-- map: Map a function over a list
--   f: function
--   l: list
-- returns
--   m: result list {f(l[1]) .. f(l[getn(l)])}
function map(f, l)
  local m = {}
  for i = 1, getn(l) do
    m[i] = f(l[i])
  end
  return m
end

Now, what I actually wanted to do was take a list of tables, each of which
has an "n" field, which is a number, and get a new list which was in the
same order as the n fields, so l[1].n == 1, l[2].n ==2 &c.

This is just a permutation, so it seemed useful to have a function that
satisfied the following :

-- permute: Permute a list
--   p: list of new positions
--   l: list to permute
-- returns
--   m: permuted list

But hang on! permute = reindex works fine!

Now I want a function

-- permuteOn: Permute a list on a given field
--   f: field whose value should be used as key
--   l: list to permute
-- returns
--   m: permuted list

But that's just

function permuteOn(f, l)
  return permute(project(f), l)
end

(where

-- project: Project a list of fields from a list of tables
--   f: field to project
--   l: list of tables
-- returns
--   p: list of f fields
function project(f, l)
  local p = {}
  for i = 1, getn(l) do
    p[i] = l[i][f]
  end
  return p
end
)

Neat, but a lot easier to understand (and use) with the extra names,
rather than the "raw" reindex.

What about transpose? Isn't that obviously a matrix transpose? Well yes,
but it's less obviously a solution to a couple of other problems: often
it's useful (if you have a functional programming background) to take some
lists:

l1 = {a1, a2,...}
l2 = {b1, b2,...}

and "zip" them together:

l3 = {{a1, b1}, {a2, b2},...}

and of course, perform the inverse operation (unzip).

In fact, it's as easy as

zip = transpose
unzip = transpose

You couldn't get away with that in ML or Haskell because it wouldn't be
well typed. So Lua lets you write less code, but it also tempts you (at
least if, like me, you have a tendency to abtract your code) to tie your
brain in knots. However, both comprehensibility and brevity can be
achieved by means of a few well-chosen aliases (zip, unzip, permute), and
one-liners (permuteOn).

To summarize: names are a useful substitute for strict types.