Comment by WJW | Hacker News Reader

Comment by WJW | Hacker News Reader

Parent Full thread

I wonder what the minimal set of data structures is that you can build all others out of. For example binary trees can be built with lists, SEXPs are proof of that. You can of course also make a (boxed) linked list out of an array of 2 pointers, with one element pointing to the value and the other to the next element. You can make arrays with just pointer arithmetic, sooooo... just pointers is enough? (I guess this can also be shown from the "other" direction, by pointing out that assembly has nothing but arithmetic and pointers)

You would also need various arithmetic operations, possibly up to hashing algorithms for hash tables/sets/bloom filters/etc. I would love to know if anyone can point me to an article or something describing the minimal set of operations needed to construct any data structure.

Any sufficiently rich data structure is probably enough on its own. Lists certainly are. For example, you don't need arithmetic separately, since you can simulate it with lists in any number of ways; e.g., the von Neumann-esque `0 = ()` and `succ n = n : n`, according to which a number is represented by a canonical list of that length. Once you can define `succ`, you can define all other arithmetic. If you're willing to give up canonical representatives, and represent a number by any list of that length, then you get an easy definition of addition by concatenation.

If you'll forgive my giving an answer that clearly wasn't what you intended, rather famously, lambdas are sufficient: https://en.wikipedia.org/wiki/Lambda_calculus. See also https://en.wikipedia.org/wiki/Combinatory_logic.

NAND gates?

For those who haven't checked either nandgame or nand2tetris out, I would recommend them as fun little diversions in boolean logic and computer architecture.

Maybe I am starting to spam the thread a bit here but I think the answer is canonical S-expressions, but proving that to be the case is more tricky than it looks although it is also kinda obvious from the surface level; vectors in s-expressions.

But yeah the real answer is lambda calculus, see lambda lisp and justine.lol

Reply on news.ycombinator.com