3 ms·
Except using only car and cdr does imply complexity—linear complexity; instead of being a constant-time operation, access to an arbitrary element in a list is O
by carussell 9y ago
Except using only car and cdr does imply complexity—linear complexity; instead of being a constant-time operation, access to an arbitrary element in a list is O(n) with respect to the length of the list.
- chriswarbo 9y agoAh yes, I didn't mean "complexity" as "computational complexity"; I use is but rather as how sprawling and difficult to understand the code must be (we could regard this formally using something like Kolmogorov complexity, but I meant it informally). One advantage of "specific" (as opposed to "generic") code, like explicit constructor/destructor pairs (e.g. named properties and accessors), is that by forcing client code to choose one particular, specific accessor, we have a lot more static information to use for optimisation; i.e. we've encapsulated the implementation behind an opaque interface, which we're free to implement in whichever way makes most efficient use of the resources we care about.