Hi David, David Kastrup <d...@gnu.org> writes:
> * libguile/srfi-1.c (scm_srfi1_length_plus): Previously, length+ > returned #f for dotted lists. This leaves the user with no efficient > means for determining the length of dotted lists. While the Scheme > standard does not prescribe a behavior here, the reference > implementation at > <URL:http://srfi.schemers.org/srfi-1/srfi-1-reference.scm> indeed > returns the spine length (number of successive pairs in the cdr-chain) > of dotted lists rather than #f, providing a good endorsement of this > behavior. > > As one consequence, the multi-list implementations for map, fold, and > for-each will happen to accept dotted lists as the shortest list. > Previously, this caused an error late during processing. In general, rationales don't belong in the commit logs. As per the GNU coding standards, change logs should only summarize the changes made. > > Signed-off-by: David Kastrup <d...@gnu.org> > --- > libguile/srfi-1.c | 28 ++++++++++++++++++++++++++-- > module/srfi/srfi-1.scm | 10 +++++----- > test-suite/tests/srfi-1.test | 28 +++++++++++++++------------- > 3 files changed, 46 insertions(+), 20 deletions(-) > > diff --git a/libguile/srfi-1.c b/libguile/srfi-1.c > index aaa3efe..0db6388 100644 > --- a/libguile/srfi-1.c > +++ b/libguile/srfi-1.c > @@ -614,8 +614,32 @@ SCM_DEFINE (scm_srfi1_length_plus, "length+", 1, 0, 0, > "circular.") > #define FUNC_NAME s_scm_srfi1_length_plus > { > - long len = scm_ilength (lst); > - return (len >= 0 ? SCM_I_MAKINUM (len) : SCM_BOOL_F); > + /* This uses the "tortoise and hare" algorithm to detect "infinitely > + long" lists (i.e. lists with cycles in their cdrs), and returns #f > + if it does find one. > + > + Dotted lists are treated just like regular lists, returning the > + length of the spine. This is in conformance with the reference > + implementation though not explicitly defined in the standard. */ > + long i = 0; Please use 'size_t' instead of 'long'. > + SCM tortoise = lst; > + SCM hare = lst; > + > + do { > + if (!scm_is_pair (hare)) return scm_from_long (i); scm_from_size_t > + hare = SCM_CDR(hare); > + i++; > + if (!scm_is_pair (hare)) return scm_from_long (i); Ditto. > + hare = SCM_CDR(hare); > + i++; > + /* For every two steps the hare takes, the tortoise takes one. */ > + tortoise = SCM_CDR(tortoise); > + } > + while (!scm_is_eq (hare, tortoise)); Please follow the GNU conventions for indentation. > + > + /* If the tortoise ever catches the hare, then the list must contain > + a cycle. */ > + return SCM_BOOL_F; > } > #undef FUNC_NAME Otherwise, this function looks good to me, but I'd prefer to give it a new name and move it into list.c, rather than extending SRFI-1's 'length+'. Hmm, coming up with names is hard. Maybe 'length*'? Thanks, Mark