On 27/09/2019 15:22, John Cowan wrote:
> I think the first method is clearly superior.  Of the usual data
> structures, only lists normally take O(n) time to get the length.  In any
> case, R7RS `write` already has to do this in order to know where to insert
> datum labels.

Yeah. Implementation tip: memoize sub-sequence lengths, otherwise
writing ((1)) works out the length of (1) to write the length for the
whole expression, then again to write the length for the (1) expression,
as it were.

As for the larger issue of whether compound objects should have a byte
length or an elements-length:

Code to write with element-counts only needs to spend O(length of list)
rather than O(number of atoms in entire subexpression) scan, without
needing that memoization code: this means less code and less working RAM
used on encoding.

Code to read with element-counts needs to recurse through all the
sub-expressions to find the end, and can't just skip it.

If skipping parsing subexpressions isn't a desired feature, then
element-counts win; so is skipping subexpressions at read time desired?

--
Alaric Snell-Pym   (M7KIT)
http://www.snell-pym.org.uk/alaric/