Your solution has a main problem: you treat a list almost like an array, by using
list-ref to get the n-th element of the list, to rebuild the list by consing all the elements from the last to the first.
This is a problem for two reasons:
it makes your procedure of order of complexity n², instead of n, as we can obtain with other algorithms, since the
list-ref has a cost of the order of n, the length of the list, and you call it a number of times which is equal to n;
if you use lists instead of arrays, you should try to use as much as possible the primitive operators on them, like
cons, that can be considered as more “natural” for this kind of data structure, having a constant cost, and resort to operators like
list-ref only when strictly necessary (otherwise you can use directly arrays, also availables in lisp languages).
So the question is: how can we implement an efficient list
reverse operator by using the primitive operators on lists?
A solution can be found if we generalize a little bit the reverse function, and instead of defining a function that reverses a list, we define a function that takes two lists as parameters, and build a new list by reversing the elements of the first one consing them on the second. This can be done in this way:
(lambda (first-list second-list)
(if (null? first-list)
(reverse1 (cdr first-list) (cons (car first-list) second-list)))))
The efficiency is given by the fact that we are using only the operators
cdr, and we scan only the first list, and only once, by adding each element to the second list.
And to obtain the
reverse function, we need simply to call the previous function with a second list as the empty list, as this will produce as result the reverse of the first list:
(reverse1 ls '())))
Actually, this technique is more commonly note as resorting to an accumulator to produce a result, and a solution like the above is more usually written in a single function in Racket:
(lambda (ls [accumulator '()])
(if (null? ls)
(reverse (cdr ls) (cons (car ls) accumulator)))))
Here we use the possibility of defining a default value for a parameter, so that the first time we call the function with the list to be reversed, and the second parameter is automatically assigned the empty list, while in the recursive call it is passed explicitly by building the (partial) result.
A final important note: the recursion in this function is called “tail recursion”, since the last operation of the function is just a call to the function itself, and the result of this call is the result of the function. In Scheme, and Racket, as well as in other similar languages with good compilers, this kind of recursion is compiled as iteration, making the function more efficient in terms of space used.