[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: [PoC] Tables aren't Lua's only data structure.**
**From**: Gavin Wraith <gavin@...>
**Date**: Fri, 17 Apr 2015 09:52:13 +0100

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/