lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

Am 20.11.2013 03:38 schröbte H. Conrad Cunningham:
On Tue, Nov 19, 2013 at 12:33 PM, Fabien <> wrote:

A fun experiment would be to add a purely functional (non-mutable)
container in Lua, and see how well it could cohabitate with imperative
tables (the result would probably not feel lua-ish at all; maybe more
scheme-ish). But my experience is, it rapidly becomes painful to pretend
that tables can be used functionally.

I am a Lua newbie (4 months), but my self-assigned task for the past 2.5
months has been to teach a course that uses Lua to explore a few issues in
programming languages.  For an early part of the course, I taught my
students a bit of functional programming. It mostly worked, but one feature
I did miss was the hierarchical list structures I was accustomed to using
in Haskell, Scala, etc.  I did an "example" module in which I implemented
what I called "cell lists" using a table as a "cons" cell. It was fun, but
I suppose these are quite inefficient structures.

Why is that? This basically boils down to a linked list, which is still a suitable data structure for a lot of use-cases. Using tables for cons cells just adds some constant hashing overhead (you could minimize that by using small integer keys instead of "head" and "tail").

In "Structure and Interpretation of Computer Programs" there is an implementation of cons-cell-lists using closures[1]. Something along the lines of:

    local function cons( hd, tl )
      return function()
        return hd, tl

    local function head( lst )
      return (lst())

    local function tail( lst )
      local _, v = lst()
      return v

    local function list( ... )
      local n, c = select( '#', ... ), nil
      for i = n, 1, -1 do
        c = cons( select( i, ... ), c )
      return c

    local function length( lst )
      if lst == nil then
        return 0
        return length( tail( lst ) ) + 1

    local function map( f, lst )
      if lst == nil then
        return nil
        return cons( f( head( lst ) ), map( f, tail( lst ) ) )

    local function filter( p, lst )
      if lst == nil then
        return nil
      elseif p( head( lst ) ) then
        return cons( head( lst ), filter( p, tail( lst ) ) )
        return filter( p, tail( lst ) )

    return {
      cons = cons,
      head = head,
      tail = tail,
      list = list,
      length = length,
      map = map,
      filter = filter,

If you really want all those type checks, I would use a weak table to keep track of all the functions that are in fact cons-cells.