implement length in r5rs scheme (drracket) [closed]

Question

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.

Closed 9 years ago.

Is it possible to implement the R5RS scheme function "length" using the car and cdr family of functions? If so could someone post the implementation?

Thanks,

Answer 1

Of course, it's pretty simple. I'm not giving a straight answer because this looks like homework and anyway it's trivial to write. Fill-in the blanks:

(define (length lst)
  (if <???>              ; if the list is empty
      <???>              ; return 0
      (<???>             ; otherwise add 1 and
       (length <???>)))) ; advance the recursion over the rest of the list

Notice that only cdr is used. We're not interested in the actual contents of the list, so we can ignore car.

Answer 2

Óscar López's answer is correct. Here are two more implementations (again with the fill-in-the-blanks).

The first one is a left-fold solution (contrast with Óscar's solution, which is a right-fold one):

(define (length lst)
  (let loop ((lst lst)
             (count 0))
    (if <???>                   ; if the list is empty
        <???>                   ; return the count
        (loop <???> <???>))))   ; otherwise bump the count and continue down the list

This has the advantage of being tail-recursive, whereas the right-fold version isn't.

The second one is a tortoise-and-hare solution, which allows cyclic lists to be detected (the earlier solutions would run forever if given a cyclic list):

(define (length lst)
  (if (null? lst)
      0
      (let loop ((tortoise lst)
                 (hare (cdr lst))
                 (count 1))
        (cond ((eq? tortoise hare) #f)                   ; found a cycle
              ((null? hare) <???>)                       ; reached end of list
              ((null? (cdr hare)) <???>)                 ; reached end of list too
              (else (loop <???> <???> (+ count 2)))))))  ; bump the count and keep looking