Racket 'list-ref' implementation half-working

Question

This is a problem from a previous assignment I worked on. We're currently programming in Racket with DrRacket and being early in the semester are just finishing a review of natural recursion.

The specific problem was to complete an implementation of list-ref by finishing the nested nth-cdr within. Here was the code given:

(define list-ref
  (lambda (ls n)
   (letrec
      ((nth-cdr
        (lambda (n)
         ;;body of function
    (car (nth-cdr n)))))

Pretty straight forward, the instructions were to implement a naturally recursive version of nth-cdr. Here's what I ended up with:

(define list-ref
  (lambda (ls n)
   (letrec
       ((nth-cdr
        (lambda (n)
          (cond  
            ((zero? n) ls)
            (else (list-ref (cdr ls) (sub1 n)))
            ))))
     (car (nth-cdr n)))))

Passing nth-cdr any number other than 0 results in a 'contract violation' of car in the body of the letrec.

(list-ref '(1 2 3) 0) ==> '1
(list-ref '(1 2 3) 1) ==> *expected: pair?* *given: 2*

Is it a problem with the scope of ls within nth-cdr? I have no idea why the body of let-rec would take the car of nth-cdr n and complain about the output?

Anyone have the answer to the likely very simple problem?

Answer 1

list-ref is easy to write as a tail-recursive function:

(define (list-ref lst n)
  (if (zero? n)
      (car lst)
      (list-ref (cdr lst) (- n 1))))

---

Update: Your solution must follow the template, you say? Here's a hacky way to do it, but unlike Óscar's solution, it does not use set!. But it's still ugly:

(define list-ref
  (lambda (ls n)
    (letrec
        ((nth-cdr
          (lambda (n)
            (if (number? n)
                (nth-cdr (cons ls n))
                (let ((ls (car n))
                      (n (cdr n)))
                  (if (zero? n)
                      ls
                      (nth-cdr (cons (cdr ls) (- n 1)))))))))
      (car (nth-cdr n)))))

Answer 2

Your helper procedure must advance over both the list and the index, it won't do to just decrement the number. And it should call itself, not the outer procedure! Also, a bit of error checking won't hurt, try this:

(define list-ref
  (lambda (ls n)
   (letrec
       ((nth-cdr
        (lambda (ls n)
          (cond
            ((null? ls) #f)
            ((zero? n) (car ls))
            (else (nth-cdr (cdr ls) (sub1 n)))
            ))))
     (nth-cdr ls n))))

To be clear, there really isn't any need for a helper procedure here, to simplify we could do this:

(define list-ref
  (lambda (ls n)
    (cond
      ((null? ls) #f)
      ((zero? n) (car ls))
      (else (list-ref (cdr ls) (sub1 n))))))

UPDATE

Now that you've mentioned in the comments that there are some additional restrictions, I can offer you the following solution - it works, but believe me, it's ugly. We shouldn't have to mutate state for this simple problem, which could be avoided by passing an additional parameter. Anyway, here you go:

(define list-ref
  (lambda (ls n)
    (letrec
        ((nth-cdr
          (lambda (n)
            (cond ((null? ls) '(#f))
                  ((zero? n) ls)
                  (else
                   (set! ls (cdr ls))
                   (nth-cdr (sub1 n)))))))
      (car (nth-cdr n)))))