4 ms·
It is, but I do wonder if it's the most performant option. For grabbing individual elements, cadddr and friends are O(N) for linked lists while a O(1) implement
by mumblemumble 5y ago
It is, but I do wonder if it's the most performant option. For grabbing individual elements, cadddr and friends are O(N) for linked lists while a O(1) implementation is possible for arrays.
List eaters are an elegant design pattern, especially for picking apart recursive algorithms, but eating linked list wouldn't be nearly as cache-friendly as map/reduce over an array. It wouldn't get rid of all the pointer chasing, but even reducing one level of it is worth something.
Perhaps, with modern language implementation technology, we could produce something like that, while also preserving persistence (at the semantic level), by, in the background, choosing mutation when there's only a single active reference to the list, and falling back to a copy-on-write discipline when there are multiple concurrent references.
For what it's worth, I find I never program that way in Clojure. I realize Clojure not being as list-oriented is a point of contention for many people, and I'm not all that much of a lisper, so perhaps my opinion isn't worth much, but I've generally found that Clojure gives me most of what I want. I am more annoyed by the lack of reader macros. Though I also understand and respect Rich Hickey's decision there.
- jhgb 5y ago> For grabbing individual elements, cadddr and friends are O(N) for linked lists That doesn't really make sense. cadddr is O(1), and so are all its c[ad]{1,4}r friends. > For what it's worth, I find I never program that way in Clojure. I suspect you don't do that because the language doesn't support it well. Which is fine, since going against the grain of a language is generally inadvisable, but it says nothing about the technique in itself.
- mumblemumble 5y agoFor a linked list implementation, car requires traversing one cons cell, cadr requires traversing two, caddr three, four for cadddr, and so on. That's about as textbook an example of O(N) as you can get.
- jhgb 5y agoBut your N is bounded from above to 4, so pretty much anything using these functions won't be unbounded in time just because of use of these functions. If you're suggesting that using nth or elt on a list of arbitrary length is a bad idea, then yes, it is, but I certainly wasn't suggesting that.