[r6rs-discuss] Proposed features for small Scheme, part 4F: more symmetry
bear at sonic.net
Thu Nov 5 16:34:25 EST 2009
On Thu, 2009-11-05 at 14:55 -0500, John Cowan wrote:
> Quite true. In addition, it used to be true that vectors had O(1) access
> and lists O(N); now they both have O(N) access, but the constant factor
> is hugely larger for lists.
Can you unwrap that comment a bit? I do not recall any scheme standard
that placed a constraint of any kind on access time. Nor have I seen
any non-toy implementation that had O(N) access for vectors. At worst
I have seen O(logN) for resizable vectors, but the standard does not
require resizable vectors.
> Still, if this is really idiosyncratic of me (does everyone else reach
> for a list first, and have to be convinced that a vector is the Right
> Thing?), I'll leave it out, I suppose.
In some cases I've been known to hold data in a list during one part
of the program (while accumulating it and before finding out how much
of it there is) then convert it to a vector for the next phase in
processing (sorting and searching once the number of elements is
stable) and convert it to a list again when the usage patterns
change again. So yeah, interconversion is useful.
'make-list' can be useful with 'apply' (when you already have a list)
when you want to make a copy of a list that you're about to operate
> I *am* having second thoughts about EMPTY-STRING? and EMPTY-VECTOR?,
> though, precisely because we do recurse on lists but normally loop
> through strings and vectors.
When programming in a recursive pattern with vectors, one usually
recurses with an advancing index. The base-case is usually expressed
as (>= index (vector-length vec)).
I would find a predicate (index-valid? num vec) useful. It would
'simplify' the common expression, could detect some additional
error conditions (negative or inexact index, for example) and
requires less mental parsing. But it's inessential. Maybe if I
write a SRFI for general programming utility functions I'd include
it along with its simple definition.
More information about the r6rs-discuss