Email list hosting service & mailing list manager

LENGTH+ implementation accepts dotted list Chris Hanson (13 Nov 2022 11:24 UTC)
Re: LENGTH+ implementation accepts dotted list Marc Nieper-Wißkirchen (13 Nov 2022 11:41 UTC)
Re: LENGTH+ implementation accepts dotted list Lassi Kortela (13 Nov 2022 15:29 UTC)
Re: LENGTH+ implementation accepts dotted list Shiro Kawai (18 Nov 2022 09:40 UTC)

Re: LENGTH+ implementation accepts dotted list Lassi Kortela 13 Nov 2022 15:28 UTC

Here's a procedure I wrote once as an exercise:

;; If object is...
;; * non-null and non-pair  returns 0; object
;; * the empty list         returns 0; ()
;; * a proper list          returns length; ()
;; * a dotted list          returns length; cdr of last pair
;; * a circular list        returns length before cycle; first pair of cycle
;;
;; The precise meaning of "length" is "number of pairs". Since list
;; elements are stored in the "car" of each pair, the number of pairs
;; is equal to the number of elements.
;;
;; <https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoise_and_Hare>

(define (length-tail object)
   (let detect-cycle ((len 0) (slow object) (fast object))
     (cond ((not (pair? fast))
            (values (* 2 len) fast))
           ((not (pair? (cdr fast)))
            (values (+ 1 (* 2 len)) (cdr fast)))
           ((not (and (eq? slow fast) (> len 0)))
            (detect-cycle (+ 1 len) (cdr slow) (cdr (cdr fast))))
           (else
            (let find-cycle-start ((len 0) (slow object) (fast fast))
              (if (eq? slow fast) (values len slow)
                  (find-cycle-start (+ len 1) (cdr slow) (cdr fast))))))))