MAPing Sequences

[Barry Margolin <barmar@Think.COM>]

    Date: 30 Mar 87 09:35:33 EST
    From: primerd!DOUG@ENX.Prime.PDN

    To:       commonlisp (common-lisp@sail.stanford.edu)
    From:     Doug Rand (DOUG@ENX.PRIME.COM) x4182 bldg 10
    Date:     30 Mar 87  9:26 AM
    Subject:  Re: MAPing Sequences

    >.. an inefficient implementation technique that doesn't support them
    > seems like a poor reason to not allow them.
    > Kelly Murray

    How can one handle circular lists indescriminately in sequence
    functions? It seems to me that at minimum the function must record or
    mark each cons to avoid a recursive loop.   Am I missing an obvious point?

Not obvious, but fairly well known.  It is not necessary to mark every
element of a list in order to detect circularity.  The easiest way I
know of to detect circularity (I think this is Plummer's algorithm) is
to scan the list simultaneously by ones and twos, i.e.  (defun
circular-list-p (list)
  (do ((l1 list (cdr l1))
       (l2 (cdr list) (cddr l2)))		;not very robust, it'll
						;lose on dotted lists
      ((or (endp l1) (endp l2)) nil)
    (when (eq l1 l2)
      (return t))))

This takes time linear in the length of the circularity plus the length
of the subsequence before the circularity begins, and constant space; I
don't know if a more efficient algorithm is known.

As for mapping functions, as long as you require that at least one of
the arguments be finite, they shouldn't have to "detect" circularities
at all.  When one of their inputs runs out they should throw out of the
loop.