How to double a list using tail recursive?

Question

(define (lst-double-helper lst acc)
  (if (empty? list)
      acc
      (lst-double-helper (rest lst) (cons (* (first lst) 2) acc))))

(define (lst-double lst)
  (lst-double-helper lst '()))

I feel I'm doing it in the right way. But this gives me an error

(lst-double '(1,2,3))
*: contract violation
  expected: number?
  given: ',2
  argument position: 1st
  other arguments...:

Why do it expect the second argument to be a number?

Answer 1

One such way is by using continuation-passing style. Here we add a parameter named return which effectively encodes a return-like behavior with a lambda. double now takes two arguments: the list to double, xs, and the continuation of the result, return –

(define (double xs return)
  (if (empty? xs)
      (return empty)
      (double (cdr xs)
              (lambda (result)
                (return (cons (* 2 (car xs))
                              result))))))

As an example, the result of double applied to a list of '(1 2 3) is sent to print

(double '(1 2 3) print)
;; '(2 4 6)
;; => #<void>

double evaluates to whatever the final continuation evaluates to; in this case, print evaluates to #<void>. We can use the identity function to effectively get the value out –

(double '(1 2 3) identity)
;; => '(2 4 6)

Racket allows you to easily specify default arguments, so we can modify double to use identity as the default continuation

(define (double xs (return identity))
  ;; ...
  )

This style results in convenient programs that work in two call styles at simultaneously: continuation-passing style –

(double '(10 11 12) print)
;; '(20 22 24)
;; => #<void>

(double '(10 11 12) length)
;; => 3

(double '(10 11 12) car)
;; => 20

(double '(10 11 12) cdr)
;; => '(22 24)

... or in direct style, using the default identity continuation

(print (double '(10 11 12)))
;; '(20 22 24)

(length (double '(10 11 12)))
;; => 3

(car (double '(10 11 12)))
;; => 20

(cdr (double '(10 11 12)))
;; => '(22 24)

Answer 2

For nested lists:

(define (atom? x)
  (and (not (null? x))
       (not (pair? x))))

(define (lst-double-helper lst acc)
  (cond ((empty? lst) acc)
        ((atom? (car lst)) (lst-double-helper (rest lst) (cons (* (first lst) 2) acc)))
        (else (lst-double-helper (rest lst) (cons (lst-double (first lst))
                                         acc) ))))

(define (lst-double lst)
  (reverse ; required to restore original order
   (lst-double-helper lst '())))

but actually to make this function tail-recursive is a little bit meaningless, because as @simmone mentioned, map would do it

(define (list-doubler lst) 
  (map (lambda (x) (* 2 x)) lst))


(list-doubler '(1 2 3))
;; '(2 4 6)

Answer 3

A couple of comments:

• List elements are separated by spaces, not commas. That's the error being reported.
• The base case of the recursion must refer to the parameter lst, not to list.
• Your tail-recursive solution reverses the list, an extra reverse is needed at the end to restore the original order

With the above changes in place, it works as expected:

(define (lst-double-helper lst acc)
  (if (empty? lst) ; parameter is called `lst`
      acc
      (lst-double-helper (rest lst) (cons (* (first lst) 2) acc))))

(define (lst-double lst)
  (reverse ; required to restore original order
   (lst-double-helper lst '())))

(lst-double '(1 2 3)) ; use spaces to separate elements
=> '(2 4 6) 

Be aware that a tail-recursive solution that traverses an input list and conses its elements to build an output list, will necessarily reverse the order of the elements in the input list. This is ok, and it's normal to do a reverse at the end. Possible alternatives to avoid reversing the elements at the end would be to reverse the input list at the beginning or to write a non-tail-recusive solution.

Answer 4

use map.

(map (lambda (a) (* a 2)) '(1 2 3))