Re: [PoC] Tables aren't Lua's only data structure.

[Gavin Wraith <gavin@...>]

In message <55308958.7070802@gmail.com>
          "Soni L." <fakedme@gmail.com> wrote:

> I'm here to show you how tables aren't actually Lua's only data 
> structure. 

Hold on! Any datatype is representable in a higher-order language,
i.e. one in which functions are first class citizens. You only
need functions. Two classical examples:

1.Booleans (* -> (* -> *))
   true = function(x) return function(y) return x end end
   false = function(x) return function(y) return y end end
2.List(A) ((A -> (* -> *)) -> (* -> *)
   emptylist = function(f) return function(x) return x end end
   cons = function(a, mylist) return function(f) 
            return function(x) return f(a)(mylist(f)(x)) end end end

There is a standard way of getting these formulae. Express the
datatype in terms of its universal properties using the second-order
polymorphic lambda calculus, then strip types. For example Booleans
are the universal ways of choosing one of two options. Lists of things
of type A are the universal way of producing a function (* -> *)
out of a way of translating things of type A to functions (A -> (* -> *))
- just compose all the translated elements of the list.

OK, it may not be an efficient way of representing the datatype, but
that is a different story.  
See http://en.wikipedia.org/wiki/System_F

-- 
Gavin Wraith (gavin@wra1th.plus.com)
Home page: http://www.wra1th.plus.com/