Understanding a tail-recursive vector

Question

I have a tail-recursive function which converts a vector into a list. I understand each line individually, but have a couple questions:

Firstly, in the code what does the code cons ((vector-ref v i) r) (- i 1) mean? (Marked "Q1".) I know that it takes the i'th element of vector v and concatenates it with i-1, but why have to be i-1? Why not work with i+1? e.g. if the vector v length is total 5, then element number 5 is concatenated with the number 4. I understand that it is making the vector list, but why work with i-1 (reducing)? Can anyone give me an explanation?

(define vector->list:rec
 (lambda (v)
   (letrec ((helper
          (lambda (vec r i)
            (if (< i 0) 
                r
                (helper vec (cons (vector-ref v i) r) (- i 1))  ;; Q1
                ))))
     (if (> (vector-length v) 0)  ;; line 9
      (helper v (cons (vector-ref v (- (vector-length v) 1)) '()) (- (vector-length v) 2))
      '()))))

Answer 1

The reason why i is decreasing with each call is that i is used to determine when we've reached the end of the vector. The idea is that when we call the helper function initially, we set i to be the length of the vector (minus 2), and then in each recursive call decrease i by 1 until it becomes less than 0, at which point we know that we've gone through the whole vector.

The issue causing your confusion, I believe, is that you're parsing the cons call incorrectly- counting the parentheses shows us that the call is really (cons (vector-ref v i) r) - the (- i 1) is just the third argument to helper.

Finally, the idea of checking in line 9 that the length of the vector is greater than 0 is that if the vector's length is 0, we just want to return an empty list '(); if we didn't do this check, then the call to (vector-ref v (- (vector-length v) 1)) would become (vector-ref v -1) if we input an empty vector, which would obviously fail. I'm not sure what you mean by "total length checking", but (vector-length v) does indeed return the entire length of v.

Answer 2

It's very helpful to use print statements judiciously to understand how a recursive function works. I added

      (print r)

right below

      (lambda (vec r i)

I ran the command:

(vector->list:rec (vector 1 4 6 8 9 10))

Here's the output:

(10)
(9 10)
(8 9 10)
(6 8 9 10)
(4 6 8 9 10)
(1 4 6 8 9 10)
=> (1 4 6 8 9 10)

When helper is called the first time, it is called using a list whose only item is the last item of the vector:

      (cons (vector-ref v (- (vector-length v) 1)) '())

which could have been made simpler by using

      (list (vector-ref v (- (vector-length v) 1)))

Answer to Q1

The line

            (helper vec (cons (vector-ref v i) r) (- i 1))  ;; Q1

prepends (in scheme, conses) the i-th element of the vector to a list that contains the i+1-th and above items of the vector.

In the example that I ran, when i is 3, r is (9 10).

If I understand you correctly, this is opposite of what you thought this statement did.

This function recurses from highest valid value of i and decrements in every recursive call. That's what you have (- i 1) as the last argument of the above call to helper.

Answer to "Also, where is the total length checking?"

The line

 (if (> (vector-length v) 0)  ;; line 9

does check whether the total length of the input is greater than 0. Only then it goes through the trouble of calling helper. Otherwise, it simply returns an empty list.

Hope that made some sense.