4 ms·
That's not quite it; it's not really about functional vs imperative (though there's some loose correlation) Common Lisp isn't purely functional (it's arguably
by brundolf 5y ago
That's not quite it; it's not really about functional vs imperative (though there's some loose correlation)
Common Lisp isn't purely functional (it's arguably the least-functional of the major Lisps), and in fact it has a vector data structure of its own, so you could make the same mistake there if you went out of your way to. Similarly, Rust has a LinkedList in its standard library. This algorithm is simply O(N) if you do it with a linked-list, and O(N^2) if you do it with a naive vector, regardless of language or programming style.
- tux3 5y agoFair enough, though I would argue Rust's Vec being the 'default' data structure plays a big role in non-beginners avoiding that mistake, versus Lisp where you more rarely see people reaching for vectors (though they exist). I have, in fact, never seen Rust code using a linked-list in the wild, though obviously there are many valid uses cases where linked lists beat vectors (and I probably don't need to tell you =]), and surely there are many examples. And the same goes for C++, you don't reach for std::list without a specific reason. Those de-facto 'defaults' in traditional 'vaguely imperative/systems' languages steer people towards different code styles. Of course both have access to all mainstream data structure, but I'd like to think the author does know about the complexity of linked-lists versus vectors, they only made that mistake because they probably don't reach for vectors as often in Common Lisp as someone in Rust would — or presumably they would have quickly gained an innate eye for expensive copies in recursive functions