3 ms·

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 t

by WJW 4y ago

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.

tmtvl 4y ago
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.
openfuture 4y ago
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
JadeNB 4y ago
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 https://en.wikipedia.org/wiki/Lambda_calculus. See also https://en.wikipedia.org/wiki/Combinatory_logic https://en.wikipedia.org/wiki/Combinatory_logic.

by WJW 4y ago

tmtvl 4y ago

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.

openfuture 4y ago

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

JadeNB 4y ago

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 https://en.wikipedia.org/wiki/Lambda_calculus. See also https://en.wikipedia.org/wiki/Combinatory_logic https://en.wikipedia.org/wiki/Combinatory_logic.