Adding all numbers in strict cons-based list is O(n). Adding all numbers in lazy cons-based list is O(n). Adding all numbers in a strict cons-based tree can be O(log n). Adding all numbers in a lazy cons-based tree can be O(log n). Laziness is an entirely different problem from the one the author is talking about.
I see many people here in the sibling replies appear to have also so thoroughly internalized that "cons is for a list" that they appear to have entirely missed the point of the article.
The author of the post here. It seems Steele might be vindicated at the end, not on the technical level but on the social level: get rid of cons, and all the mental assumptions coming with it, for truly parallel solid data structures and algorithms that would go with them.
In Scheme, we have streams for lazy lists.
I get the point about getting rid of cons. You don't need the actual cons data structure; just the accessor abstraction. In TXR Lisp, I define car and cdr for objects other than conses. They are defined in a way that obeys "nil correctness".
$ txr -p '(list (car "ab") (cdr "ab") (cdr "a"))'
(#\a "b" nil)
So, with a repeating lazy list and a string, we can do the Vigenère cipher in one line:
$ txr -p '[mapcar (ret `@1@2`) "abcd" "1234"]'
("a1" "b2" "c3" "d4")
Watch what happens with mappend:
$ txr -p '[mappend (ret `@1@2`) "abcd" "1234"]'
"a1b2c3d4"
Wait, mapcar has that hack too!
$ txr -p '[mapcar + "abcd" #(0 1 2 3)]'
"aceg"
The LCONS is a binary cell which has an associated function. It begins life in a "promised" state. When the CAR or CDR of a LCONS is accessed for the first time, the LCONS is "forced": the function is called, and stuffs values into the CAR and CDR. Then it is dissociated from the LCONS, which behaves like a CONS after that.
In the Lisp dialect built into the TXR tool, I have conses as well as lazy conses. Lazy conses satisfy the consp function, and behave like conses for most intents and purposes.
Lazy conses give you structures that you can feed to functions that expect ordinary conses. Many of those functions instantly become empowered for lazy processing; suddenly they can handle infinite lists.
For some functions, you can easily provide lazy equivalents. A lazy mapcar returns a lazy list, which applies a function to tuples of other lazy lists.
Add the infinite sequences {0, 1, 2, ...} and {10, 11, 12, ...}, then take the first ten elements of the result:
If you use regular mapcar, it will hang in a loop up trying to construct the whole list as it fills memory.