How efficient is (Guile) Scheme's reverse function

Question

It is very easy to use Scheme's reverse function, for example after creating a list in reverse order with (cons new-obj my-list) rather than (append my-list (list new-obj)).

However, I'm wondering how efficient that part would be. If a Scheme list is a singly linked list (as I assume) that would imply traveling through the whole list at least once to reach the last element, isn't it? And this would require reverse to somehow create the backlinks along the way?

OTOH in a doubly-linked list one would simply traverse the list from the end to the start, which would be more efficient.

My question is: if I have a situation where a program generates a list (in reverse order) and at some point processes the whole list is it worth bothering to implement that processing in a way that it can handle the list in reverse order, or is it no penalty to simply use reverse first?

This is for Guile Scheme, and Guile 1.8 to be specific (if it makes a difference).

"a doubly-linked list one would simply traverse the list from the end to the start, which would be more efficient." that is, assuming that you have a pointer to the last element. — Óscar López, Jul 11 '18 at 08:09
Benchmark! This blog post defines several versions of `append`. Try to predict which one is fastest on Guile. Then try it. Prepare to be surprised. http://www.scheme.dk/blog/2007/05/know-your-implementation.html — soegaard, Jul 11 '18 at 13:23
The vital missing piece of information in your question: how long are your lists, and how many times will you be reversing them? If your lists are less than 50K elements, and you're reversing them relatively infrequently, you definitely shouldn't worry about it. — John Clements, Jul 11 '18 at 18:12

Will Ness · Answer 1 · 2018-07-11T16:34:45.453

Reversing takes O(n) time to create the n-long reversed list, so takes O(n) space as well. You have only traverse the original list once to reverse it.

If the original list isn't used anymore, it could be garbage collected (when? becomes the question) and its memory reclaimed, for the overall theoretical O(1) space cost; but garbage collecting has its own costs.

So, test, and if your lists are long and you see lots of garbage collecting going on, do what you suggested. It will more or less halve your time and space requirements (in that segment of the code base).

But if the list-building and reversing takes up 0.0001% of your overall time and space, halving that won't be such a huge improvement.

There are no back links in singly-linked lists, by the way. The reversing simply builds new cons cells as it traverses the original one, by the repeated consing.

This answer provides valuable explanations. However, I chose the other answer due to the code examples. — uli_1973, Jul 11 '18 at 12:07

Óscar López · Accepted Answer · 2018-07-11T08:14:03.983

There will be a penalty in using the built-in reverse procedure, which is O(n) in time complexity and O(1) in space complexity, and looks similar to this (and yes, we have to traverse the list until the end, creating backlinks along the way):

(define (reverse lst)
  (let loop ((lst lst) (acc '()))
    (if (null? lst)
        acc
        ; notice the tail recursion!
        (loop (cdr lst) (cons (car lst) acc)))))

On the other hand, I wouldn't worry too much about it, unless the lists you're operating on are humongous, and your profiler demonstrates that the reverse procedure is a bottleneck.

Just use the built-in, to simplify your code - composing existing functions is the style encouraged by functional programming. In Scheme, we try to process lists in a tail-recursive way, even if that means creating a list in reverse and we need to call reverse at the end, it's totally acceptable.

score 0 · Answer 3 · answered Jul 11 '18 at 08:42

Imagine the simple copy function:

(define (copy1 lst)
  (let loop ((lst lst) (acc '()))
    (if (null? lst)
        (reverse acc)
        (loop (cdr lst) (cons (car lst) acc)))))

Versus one where you use append:

(define (copy2 lst)
  (let loop ((lst lst) (acc '()))
    (if (null? lst)
        acc
        (loop (cdr lst) (append acc (list (car lst)))))))

Both append and reverse is O(n), which means they iterate the whole list. The difference between the two versions of copy is that the version with reverse does all elements once at the end while the append version calls append for every element. That makes the last version O(n*n) and much more inefficient than the first which is O(n). With a large list you will quickly notice that difference.

Now to answer your question. You should work with a data type optimized for your task. If you always are making a list where you are appending to the end then do all the work on the list in reverse and wait for the reverse until you need it. You can even make abstractions around it.

I knew about the implications of creating lists with cons vs. append, and that I work with a list that ends up reversed. My question was if the cost of the built-in `reverse` was worth figuring out ways of working with the reversed list later on instead of first reversing it and using it in the "real-world" order. — uli_1973, Jul 11 '18 at 12:06
@uli_1973 Built in `reverse` is O(n). It depends greatly on how you use it in "real-world" order. As i write in the last part *you should model your data after the process*. None of the hard algorithms keeps their data structure in a visual pleasing order unless that is also good for the algorithm. — Sylwester, Jul 11 '18 at 17:07

How efficient is (Guile) Scheme's reverse function

3 Answers3