Re: Operators on functions

[Philipp Janda <siffiejoe@...>]

Am 20.11.2013 03:38 schröbte H. Conrad Cunningham:
> On Tue, Nov 19, 2013 at 12:33 PM, Fabien <fleutot+lua@gmail.com> 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").

> http://www.cs.olemiss.edu/~hcc/csci658/notes/658lectureNotes.html#cellList

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
      end
    end

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

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

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

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

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

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

    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.

  [1]: 
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html#%_idx_1452

> Conrad

Philipp