Scheme: Iterative process to reconstruct a list in original order?

Question

My question is: how to write a procedure that utilises tailcall, and that constructs a list not in the reverse order.
To show what I mean, here is an example of a very simple procedure that is iterative, and that creates a copy of a list:
(define (copy-list ls)
    (define (iter cp-ls rest-ls)
      (if (null? rest-ls)
          cp-ls
          (iter (cons (car rest-ls) cp-ls) (cdr rest-ls))))
    (iter '() ls))

The problem is that, due to the iterative order in which the elements are consed together, the returned list ends up reversed. Yes, you could easily solve this by doing (reverse cp-list) instead of just cp-list in the if-block, but the problem with this is that reverse is a recursive process. Utilising this procedure will nullify the tailcall advantage, which is that the stack size grows linearly with the input size.
So, basically, how to write a procedure like the one mentioned that returns the list in correct order without utilising any sort of recursive processes?
Thanks

alinsoar · Answer

(map (lambda(x) x) l)

will make a copy of the list l and it's not recursivelly written.
(let ((l '(1 2 3 4)))
  ((fold-right (lambda (e acc)
                 (lambda (x) (cons x (acc e))))
               (lambda (x) (list x))
               (cdr l))
   (car l)))

is another form to copy a list without recursion, but using a monoid.
other:
(let ((l '(1 2 3 4)))
  (car ((fold-right (lambda (e acc)
                      (lambda (x) (acc (append x (list e)))))
                    (lambda (x) (list x))
                    (cdr l))
        (list (car l)))))

other:
(let ((l '(1 2 3 4)))
  (cdr ((fold-left (lambda (acc e)
                     (lambda (x) (cons x (acc e))))
                   (lambda (x) (list x))
                   l)
        'first)))

other (suggested by Will):
(let ((l '(1 2 3 4)))
  ((fold-right (lambda (e acc)
                 (lambda (k) (k (acc (lambda (es) (cons e es))))))
               (lambda (z) (z (list))) l)
   (lambda (es) es)))

There are lots of other ways to copy a list.  In general, to make a copy, you need to call, either directly or indirectly, cons.
As mentioned in the comments, not all these ways use an iterative process.

Thank you · Answer

You can use continuation passing style, return, below -
(define (copy-list ls)
  (let loop ((ls ls) (return identity))
    (if (null? ls)
        (return null)
        (loop (cdr ls)
              (lambda (r) (return (cons (car ls) r)))))))

(copy-list '(1 2 3 4))
; '(1 2 3 4)

Here's what the process looks like -
(copy-list '(1 2 3 4))
(loop '(1 2 3 4) identity)
(loop '(2 3 4) (lambda (r) (identity (cons 1 r))))
(loop '(3 4) (lambda (r) ((lambda (r) (identity (cons 1 r))) (cons 2 r))))
(loop '(4) (lambda (r) ((lambda (r) ((lambda (r) (identity (cons 1 r))) (cons 2 r))) (cons 3 r))))
(loop '() (lambda (r) ((lambda (r) ((lambda (r) ((lambda (r) (identity (cons 1 r))) (cons 2 r))) (cons 3 r))) (cons 4 r))))
((lambda (r) ((lambda (r) ((lambda (r) ((lambda (r) (identity (cons 1 r))) (cons 2 r))) (cons 3 r))) (cons 4 r))) null)
((lambda (r) ((lambda (r) ((lambda (r) (identity (cons 1 r))) (cons 2 r))) (cons 3 r))) '(4))
((lambda (r) ((lambda (r) (identity (cons 1 r))) (cons 2 r))) '(3 4))
((lambda (r) (identity (cons 1 r))) '(2 3 4))
(identity '(1 2 3 4))
'(1 2 3 4)

Óscar López · Answer

Notice that your iter procedure is almost exactly how reverse is implemented in the first place - no, it's not a recursive process as you mention in the question.
In Racket is simple to check the definition of a procedure: in an edit window without definitions type reverse, right-click it and then select "jump to definition". It'll have a bit of extra code for optimization and error handling, but the core of the algorithm is in the letrec-values part, and it's identical to your iter procedure. So, if we already have that:
(define (reverse ls)
  (let iter ((cp-ls '()) (rest-ls ls))
    (if (null? rest-ls)
        cp-ls
        (iter (cons (car rest-ls) cp-ls) (cdr rest-ls)))))

Then, copy-list is just:
(define (copy-list ls)
  (reverse (reverse ls)))

That's not terribly useful, by the way - if you're not mutating the list, there's no point in copying it. And the reverse of a reverse is just the original thing, isn't it? In fact any implementation of copy-list that operates on immutable lists, for all intents and purposes is equivalent to the identity procedure:
(define (copy-list ls) ls)

Scheme: Iterative process to reconstruct a list in original order?

3 Answers

Add your own answers!

Ask a Question