0
(define (sqr-tail lst)
  (define (helper lst res)
    (if (null? lst)
        res
        (cond ((list? (car lst)) 
               (helper (cdr lst) 
                       (cons (helper (car lst) ())
                             result)))
              (else (helper (cdr lst)
                            (cons (expt (car lst) 2) res))))))
  (helper lst ()))

I have this tail recursion function in scheme which sqr every element in the list, but unfortunately the result is reversed to what I suppose to output.

for input :

> (sqr-tail (list 1 2 4 3 (list 1 2 (list 1)) 3 3))

the output :

< (9 9 ((1) 4 1) 9 16 4 1)

thanks.

2 Answers 2

2

This is something that is inherent in the way Lisp/Scheme lists work: because there are only really conses, the way to build up lists is backwards. So the common tail-recursive-loop-with-an-accumulator approach as you've used ends up building the result backwards. The simple answer to this is that you need to reverse the result when you return it, and in your case, since you are recursing (not tail-recursing) into nested lists as well you need to reverse them as well of course.

Here is a somewhat cleaned-up and error-protected version of your original function (note this was written in Racket -- it may not be quite legal Scheme, but it is close):

(define (square-nested-list/reversed l)
  (define (snl-loop lt accum)
    (cond [(null? lt)
           accum]
          [(cons? lt)
           (let ([head (car lt)]
                 [tail (cdr lt)])
             (cond [(list? head)
                    (snl-loop tail (cons (snl-loop head '())
                                         accum))]
                   [(number? head)
                    (snl-loop tail (cons (* head head) accum))]
                   [else (error "mutant horror death")]))]
          [else (error "mutant death horror")]))
  (snl-loop l '()))

So to get the result forwards we need to reverse the accumulator when we return it. This is a very small change to the above function:

(define (square-nested-list/forward l)
  (define (snl-loop lt accum)
    (cond [(null? lt)
           (reverse accum)]
          [(cons? lt)
           (let ([head (car lt)]
                 [tail (cdr lt)])
             (cond [(list? head)
                    (snl-loop tail (cons (snl-loop head '())
                                         accum))]
                   [(number? head)
                    (snl-loop tail (cons (* head head) accum))]
                   [else (error "mutant horror death")]))]
          [else (error "mutant death horror")]))
  (snl-loop l '()))

If you want to be annoyingly clever and purist you can now notice that the tail-recursive-loop-with-accumulator approach produces results in reverse, so the trivial case of it is, in fact, reverse:

(define (square-nested-list/forward/stupidly-purist l)
  (define (rev l)
    (define (rev-loop lt a)
      (if (null? lt) a (rev-loop (cdr lt) (cons (car lt) a))))
    (rev-loop l '()))
  (define (snl-loop lt accum)
    (cond [(null? lt)
           (rev accum)]
          [(cons? lt)
           (let ([head (car lt)]
                 [tail (cdr lt)])
             (cond [(list? head)
                    (snl-loop tail (cons (snl-loop head '())
                                         accum))]
                   [(number? head)
                    (snl-loop tail (cons (* head head) accum))]
                   [else (error "mutant horror death")]))]
          [else (error "mutant death horror")]))
  (snl-loop l '()))

People who do this are generally just trying to score points on the internet though (there are even more stupidly pure approaches for which you get more points).

And here are the results of calling those three functions:

> (define test-data '((1 2 3) (4 5) 6))
> (displayln (square-nested-list/reversed test-data))
(36 (25 16) (9 4 1))
> (displayln (square-nested-list/forward test-data))
((1 4 9) (16 25) 36)
> (displayln (square-nested-list/forward/stupidly-purist test-data))
((1 4 9) (16 25) 36)

Some other approaches

One issue with this 'reverse the result' is that it involves walking the result to reverse it, and also making a copy of it. Once upon a time this was something that was a real problem, because machines had only a tiny amount of memory and were very slow. Indeed, if your lists are enormous it still is a problem. More commonly it is a problem which exists in the minds of people who either, like me, remember machines which were very slow and had only tiny memory, or whose minds have been damaged by languages which encourage you to behave as if you were using such machines ('C programmers know the cost of everything but the value of nothing').

One partial answer to this problem offered by older Lisps is a function which is like reverse but works destructively: it reverses a list in place, destroying the original structure. This function is called nreverse in Common Lisp. If it existed in Scheme it would be called reverse! I suppose.

A more complete answer is to build the list forwards in the first place. You do this by trickery involving keeping a reference to the final cons of the list, and repeatedly replacing its cdr with a new final cons whose car is the object you are collecting. If you want to do this without your code looking horrible you need to use a macro: the one I wrote (for Common Lisp, not Scheme) was called collecting as it collected lists forwards. There are many others. Note that this approach requires mutable conses and also is not clearly efficient in the presence of modern garbage collectors.

Macros like collecting still have their place I think: not because they make your code faster, but because they can make it clearer: if you want collect some results into a list, then do that, don't do this weird reversing thing.

Sign up to request clarification or add additional context in comments.

Comments

2

You are almost there.

All you need to do is reverse the return value for each sublist:

(defun sqr-tail (lst)
  (labels ((helper (lst res)
             (cond ((null lst)
                    (reverse res))
                   ((listp (car lst))
                    (helper (cdr lst) 
                            (cons (helper (car lst) ())
                                  res)))
                   (t (helper (cdr lst)
                              (cons (expt (car lst) 2) res))))))
    (helper lst ())))
(sqr-tail (list 1 2 4 3 (list 1 2 (list 1)) 3 3))
==> (1 4 16 9 (1 4 (1)) 9 9)

or, in scheme:

(define (sqr-tail lst)
  (define (helper lst res)
    (cond ((null? lst)
           (reverse res))
          ((list? (car lst))
           (helper (cdr lst) 
                   (cons (helper (car lst) ())
                         res)))
          (else (helper (cdr lst)
                        (cons (expt (car lst) 2) res)))))
    (helper lst ()))

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.