如何使用尾递归加倍列表？

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 '()))

我觉得我的做法是正确的。但这给了我一个错误

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

为什么它期望第二个参数是一个数字？

Answer 1

使用地图。

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

Answer 2

一些评论：

列表元素由空格而不是逗号分隔。这就是报告的错误。
递归的基本情况必须引用参数lst，而不是list。
你的尾递归解决方案颠倒了列表，最后需要额外的reverse来恢复原来的顺序

完成上述更改后，它按预期工作：

(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)

请注意，遍历输入列表并cons使用其元素构建输出列表的尾递归解决方案必然会颠倒输入列表中元素的顺序。这个没问题，最后做个reverse也正常。避免在末尾反转元素的可能替代方法是在开头反转输入列表或编写非尾递归解决方案。

Answer 3

对于嵌套列表：

(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 '())))

但实际上让这个函数尾递归有点没有意义，因为正如@simmone 提到的那样，map 会做到这一点

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


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

Answer 4

其中一种方法是使用连续传递样式。在这里，我们添加了一个名为 return 的参数，它使用 lambda 有效地编码了类似 return 的行为。 double 现在接受两个参数：要加倍的列表 xs 和结果的延续 return –

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

例如，double 应用于 '(1 2 3) 列表的结果被发送到 print

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

double 计算最终延续的计算结果；在这种情况下，print 的计算结果为 #<void>。我们可以使用identity函数来有效的取出值-

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

Racket 允许您轻松指定默认参数，因此我们可以修改 double 以使用 identity 作为默认延续

(define (double xs <b>(return identity))</b>
  ;; ...
  )

这种风格产生了同时在两种调用风格下工作的方便程序：连续传递风格 –

(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)

...或直接风格，使用默认的identity延续

(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)

如何使用尾递归加倍列表？

How to double a list using tail recursive?

tail-recursion

racket