0

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))
      '()))))
user1915570
  • 386
  • 2
  • 7
  • 27

2 Answers2

1

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.

R Sahu
  • 204,454
  • 14
  • 159
  • 270
0

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.

Lily Chung
  • 2,919
  • 1
  • 25
  • 42
  • @user1915570 Yes, I was referring to *that* -2 when I wrote that. The reason is that we start off by taking the last element off in `(vector-ref v (- (vector-length v) 1))` -- that's -1 -- and in our check for the end we use `(< i 0)`. If it had been `(<= i 0)` we'd use -1, but since we're checking for a strict less-than it has to be -2 in order for it to be counted correctly. Trace through the code yourself to see what I mean. – Lily Chung May 09 '14 at 03:07
  • I'd refer you to an [existing question](http://stackoverflow.com/questions/33923/what-is-tail-recursion) on tail recursion for your second question. – Lily Chung May 09 '14 at 03:09
  • Thanks. that I understand now. I added one more question in another answer – user1915570 May 09 '14 at 03:40
  • but I don't get why we need to have line 10. Is that because it is not included inside if routine. that's only include the inner loop(?) except the last element (-1) and (-2) => because of we didn't include 0. but here line 10, it is vector element -2 (= the second last element). so it means line 10 concatenate the last element with the second last element. why we need that? – user1915570 May 10 '14 at 12:14
  • @user1915570 Line 10 is required to kick off the whole process. The call to `helper` in line 7 allows the program to loop, but in order to start the loop in the first place we need a call to `helper` in line 10. – Lily Chung May 10 '14 at 14:46
  • it seems I still only understand the definition of tail recursive. when it comes to code, it is still really unclear.. in the previous code if the line 10 : (helper vec (- (vector-length vec) 1) '()) shouldn't it be like this : (helper vec (cons (vector-ref v i) r) (i)) in Q1? – user1915570 May 13 '14 at 08:16
  • @user1915570 Your issue isn't with tail recursion, it's just with recursion in general. You need the call in line 10 just to *call* the recursive function `helper` you've defined above. Remember, that call isn't inside `helper`- `i` and `r` aren't even in scope. Without line 10, you would have defined the function `helper`, but you would never run it. – Lily Chung May 13 '14 at 13:27