In the functional world, there are all sorts of precise constructs to operate on lists (maps, folds, unfolds, scans, etc.), and many versions of these that support concurrency. That's what I imagine when you say "declarations of what needs to be done".
Even maps, folds, etc are often defined in terms of what order they process data. This is useful for early exit, and mutable state dependency between iterations. But again, this demands serialized, specifically ordered processing of elements.
Lists themselves are ordered structures. Their generalized interface does not assume it's just a bag of items easily thrown around in sub-parts, especially if the linked list nodes are to be modified.
Of course, the above applies to impure functional languages. Purely functional of course has far more freedoms, but even the Lisps and such ultimately demand sequential processing for most of their fundamental list operations.
So, it isn't just that maps are defined in terms of car/cdr, it is that the list itself is defined in terms of car/cdr. The "aha" moment is when you can see that an array of items in c can efficiently represent a tree structure where the parent/child relationships are implied, not tagged. The performance gains from this are impressive.
Every time I see a C or C++ talk discussing value types or arrays, I get to think those guys never saw other programming languages, e.g. Algol/Wirth family.
Another example of the Lady Gaga culture, instead of learning about the world of programming languages.
Look into the Scala (and clojure?) vector sometime. Literally a 32-ary tree. Makes the algorithm somewhat pleasant to look at, but are we really shocked when something using a simple array can beat it in performance?
Now, it is a perfectly fair and valid point that optimizing development time may be preferred. We are allowed contradictary valid points in situations that are trade off defined.
If you use persistent data-structures the way they are meant to be used, they can and will be faster than a simple array.
Both have valid use-cases, but they are often distinct.
Even the one you are making is... tough. Persistent data-structures are not a sure fire win against mutable versions. Again I find myself refering to the DLX algorithm. The entire point of which is that it is easier and faster to permute through different configurations of a data structure then it is to have all instances instantiated in a persistent fashion.
Does this mean that persistent data structures are without use? Of course not! Again, you may not be optimizing speed of execution. Which is perfectly valid!!