Sure, my thinking is that a cons cell can build singly linked lists and node-based binary trees. Some data structures are based only on those, but most involve an array of some kind. In scheme, for example, it's the combination of cons (i.e. lists and trees) and vector (i.e. arrays) that allows for arbitrary data structures. It's very constraining to have only the lists.
- array: not a singly-linked list.
- hash table: often an array of singly-linked lists, so not a list.
- red-black or AVL tree: can be built with cons cells.
- doubly-linked list: not a singly-linked list
- double-ended queue: array of double-ended queues, so not a list. Could also be implemented as a doubly-linked list.
So what about streams? Functions? Closures? Call/cc structures?
I understand your point if you are speaking in literal terms about just simple cons cells, but in practical Lisp/Scheme code, you don’t really rely on just the basics to do things.
I think there’s a hyperfocus sometimes on the simplicity of the core of lisp, the apply/eval balance, but it’s quite possible and often easy and convenient to perform normal programming tasks with these languages as well.
MathMonkeyMan|3 years ago
- array: not a singly-linked list.
- hash table: often an array of singly-linked lists, so not a list.
- red-black or AVL tree: can be built with cons cells.
- doubly-linked list: not a singly-linked list
- double-ended queue: array of double-ended queues, so not a list. Could also be implemented as a doubly-linked list.
adenozine|3 years ago
I understand your point if you are speaking in literal terms about just simple cons cells, but in practical Lisp/Scheme code, you don’t really rely on just the basics to do things.
I think there’s a hyperfocus sometimes on the simplicity of the core of lisp, the apply/eval balance, but it’s quite possible and often easy and convenient to perform normal programming tasks with these languages as well.