functional programming - Reversing list vs non tail recursion when traversing lists

Question

I wonder how do you, experienced lispers / functional programmers usually make decision what to use. Compare:

(define (my-map1 f lst)
  (reverse
   (let loop ([lst lst] [acc '()])
     (if (empty? lst)
         acc
         (loop (cdr lst) (cons (f (car lst)) acc))))))

and

(define (my-map2 f lst)
  (if (empty? lst)
      '()
      (cons (f (car lst)) (my-map2 f (cdr lst)))))

The problem can be described in the following way: whenever we have to traverse a list, should we collect results in accumulator, which preserves tail recursion, but requires list reversion in the end? Or should we use unoptimized recursion, but then we don't have to reverse anything?

It seems to me the first solution is always better. Indeed, there's additional complexity (O(n)) there. However, it uses much less memory, let alone calling a function isn't done instantly.

Yet I've seen different examples where the second approach was used. Either I'm missing something or these examples were only educational. Are there situations where unoptimized recursion is better?

Answer 1

When possible, I use higher-order functions like map which build a list under the hood. In Common Lisp I also tend to use loop a lot, which has a collect keyword for building list in a forward way (I also use the series library which also implements it transparently).

I sometimes use recursive functions that are not tail-recursive because they better express what I want and because the size of the list is going to be relatively small; in particular, when writing a macro, the code being manipulated is not usually very large.

For more complex problems I don't collect into lists, I generally accept a callback function that is being called for each solution. This ensures that the work is more clearly separated between how the data is produced and how it is used.

This approach is to me the most flexible of all, because no assumption is made about how the data should be processed or collected. But it also means that the callback function is likely to perform side-effects or non-local returns (see example below). I don't think it is particularly a problem as long the the scope of the side-effects is small (local to a function).

For example, if I want to have a function that generates all natural numbers between 0 and N-1, I'd write:

(defun range (n f)
  (dotimes (i n)
    (funcall f i)))

The implementation here iterates over all values from 0 below N and calls F with the value I.

If I wanted to collect them in a list, I'd write:

(defun range-list (N)
  (let ((list nil))
    (range N (lambda (v) (push v list)))
    (nreverse list)))

But, I can also avoid the whole push/nreverse idiom by using a queue. A queue in Lisp can be implemented as a pair (first . last) that keeps track of the first and last cons cells of the underlying linked-list collection. This allows to append elements in constant time to the end, because there is no need to iterate over the list (see Implementing queues in Lisp by P. Norvig, 1991).

(defun queue ()
  (let ((list (list nil)))
    (cons list list)))

(defun qpush (queue element)
  (setf (cdr queue)
        (setf (cddr queue)
              (list element))))

(defun qlist (queue)
  (cdar queue))

And so, the alternative version of the function would be:

(defun range-list (n)
  (let ((q (queue)))
    (range N (lambda (v) (qpush q v)))
    (qlist q)))

The generator/callback approach is also useful when you don't want to build all the elements; it is a bit like the lazy model of evaluation (e.g. Haskell) where you only use the items you need.

Imagine you want to find the first empty slot in a vector, you could do this:

(defun empty-index (vector)
  (block nil
    (range (length vector)
           (lambda (d) 
             (when (null (aref vector d))
               (return d))))))

Here, the block of lexical name nil allows the anonymous function to call return to exit the block with a return value.

In other languages, the same behaviour is often reversed inside-out: we use iterator objects with a cursor and next operations. I tend to think it is simpler to write the iteration plainly and call a callback function, but this would be another interesting approach too.