1
\$\begingroup\$

I am using the SICP book. There is an exercise in which you need to create a function that will receive a list as an argument and return a list with the same elements in a reverse order.

I know there are more efficient solutions than the one I am going to present. However, I really learn by analyzing things that came up naturally from my mind.

I would like to improve my suboptimal solution in its own nature.

First, I created my own list-ref (I like building built-in functions as a matter of practice):

(define (list-ref lista n)
  (if (= n 1)
      (car lista)
      (list-ref (cdr lista) (- n 1))))

Second, I created my own function to count the length of a list:

(define (list-len lista)
  (if (null? lista)
      0
      (add1 (list-len (cdr lista)))))

After that, I created the core of the reverse process:

(define (reverse-exe lista n)
  (if (= n 0)
      empty
      (cons (list-ref lista n) (reverse-exe lista (- n 1)))))

On the code above, the parameter n needs to be the length of the list (considering the first element as 1, and not zero).

As the question asks us to build a function that will receive only a list as an input, I created another function which turns "n" as the length:

(define (reverse lista)
  (reverse-exe lista (list-len lista)))

Is there a better way to organize these procedures?

\$\endgroup\$
0
\$\begingroup\$

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:

  1. 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;

  2. if you use lists instead of arrays, you should try to use as much as possible the primitive operators on them, like car, cdr, cons, that can be considered as more “natural” for this kind of data structure, having a constant cost, and resort to operators like len and 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:

(define reverse1
  (lambda (first-list second-list)
    (if (null? first-list)
        second-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 cons, car and 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:

(define reverse
  (lambda (ls)
    (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:

(define reverse
  (lambda (ls [accumulator '()])
    (if (null? ls)
        accumulator
        (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.

\$\endgroup\$
0
\$\begingroup\$

One can also use 'named let' loops to add items from one list to a new list, using cons which will reverse the order :

(define (myreverselist l)
  (let loop ((l l)
             (nl '()))
    (if (empty? l) nl             ; return new list if first is over
        (loop (cdr l)             ; else cons first item to new list and loop again
              (cons (car l) nl)))))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy