[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- 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,
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