@screwtape @riley
As a historical note:
> There isn't a lot of cost (well, one cons to nil)
Back in the days when RAM was measured in kilobytes / kilowords, some implementations did in fact have space-optimized representations for short lists represented as small arrays.
See cdr-coding
https://en.wikipedia.org/wiki/CDR_coding
That might still be in some implementations today, since its savings might be significant in large structures or in aiding cache locality.
ย
The first paper may well have been L. Peter Deutsch: A LISP Machine with Very Compact Programs. IJCAI 1973, Pages 697 - 703
This is covered in 7.13 in the classic "Anatomy of Lisp", John Allen (1937-2022), 1978 (long out of print, and the author once replied to my query saying he didn't think it was worthwhile updating it for more modern times).
Has a lot on implemention, but tends to talk about abstractions in terms of M-Expressions, which is no longer in style.
ACM has it online:
https://dl.acm.org/doi/pdf/10.5555/542865
Glowing review of "Anatomy" on goodreads: https://www.goodreads.com/book/show/1537412.Anatomy_of_LISP
"John Allen (1937-2022) and Anatomy of LISP" by Paul McJones
https://mcjones.org/dustydecks/archives/2024/04/11/1249/