• Subject: Re: Operators on functions
• From: Philipp Janda <siffiejoe@...>
• Date: Wed, 20 Nov 2013 05:26:10 +0100

```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,
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
```
```
```
```