将方案中具有两次递归调用的函数转换为尾递归

Question

在开始之前：是的，这是大学的作业。在我被告知我又懒又邪恶之前：这部分作业是转换我们已有的两个函数，这是第六个。

(define (flatten-list a-list)
  (cond ((null? a-list) '())
      ((list? (car a-list)) 
       (append (flatten-list (car a-list)) (flatten-list (cdr a-list))))
      (else (cons (car a-list) (flatten-list (cdr a-list))))))

正如您可以猜到的那样，即使列表是嵌套的，该函数也会展平列表。我的具体转换问题出现在 (list? (car a-list)) 条件中，其中我正在进行两次递归调用。我已经做了斐波那契数列，只需在尾递归上使用两个“累加器”就可以做到这一点。然而，我的头脑还没有接受过这方面的训练，还不知道应该如何进行。

如果我得到提示而不是结果，我将不胜感激。谢谢！

Answer 1

这是我的解决方案：

(define (flatten-iter a-list)
  (define (flat-do acc lst-interm lst)
    (cond 
      ((null? lst)
       (reverse acc))
      ((and (list? lst-interm) (not (null? lst-interm)))
       (flat-do acc (car lst-interm) (append (cdr lst-interm) lst)))
      ((not (list? lst-interm))
       (flat-do (cons lst-interm acc) empty lst))
      ((list? (car lst))
       (flat-do acc (car lst) (cdr lst)))
      (else
       (flat-do (cons (car lst) acc) empty (cdr lst)))))
  (flat-do empty empty a-list))

(flatten-iter (list 1 (list 2 (list 3 4 (list 5 empty 6))) 7 8))
=> (1 2 3 4 5 6 7 8)

尾递归函数要求它们永远不会返回，因此您不能使用堆栈来存储程序的状态。相反，您可以使用函数参数在函数调用之间传递状态。因此，我们需要确定如何维护状态。因为我们函数的结果是list?，所以增加一个空列表是有意义的；为此，我们使用 acc。您可以在上面的 else 分支中看到它是如何工作的。但我们应该能够处理嵌套列表。当我们深入时，我们应该保留嵌套列表的其余元素以进行进一步处理。示例列表： (list 1 (list 2 3) 4 5)

直到 (list 2 3) 我们已经将 1 添加到累加器中。由于我们不能使用堆栈，因此我们需要其他地方来存储列表的其余元素。这个地方就是 lst 参数，它包含要展平的原始列表的元素。我们可以将lst附加到其余元素(cdr (list 2 3))，即(list 3) code>，然后继续我们在展平时偶然发现的列表头部，即 (car (list 2 3))，它只是 2。现在， (and (list? lst-interm) (not (null? lst-interm))) 成功，因为 flat-do 是这样调用的：

(flat-do (list 1) (list 2 3) (list 4 5))

并且条件触发此代码：

(flat-do (list 1) (car (list 2 3)) (append (cdr (list 2 3)) (list 4 5)))

flat-do 再次以这种方式调用： (flat-do (list 1) 2 (list 3 4 5))

条件 (not (list? 2)) 现在成功，并且代码 (flat-do (cons 2 1) empty (list 3 4 5)) 被评估。

其余处理通过 else 分支完成，直到 lst 为 null? 并在 acc 上执行 reverse 。然后函数返回反转后的累加器。

Answer 2

我们可以遵循 John McCarthy 的 gopher 技巧的灵感，即通过旋转列表（虽然，这里不是外科手术，而是虚拟的，即使用参数）：

(define (flatten lst)
  (flat (reverse lst) empty))

(define (flat lst rs)
  (cond
     ((null? lst) rs)
     ((null? (car lst))
       (flat (cdr lst) rs))
     ((not (pair? (car lst))) ;; atom? (car lst)
       (flat (cdr lst) 
             (cons (car lst) rs)))
     (else
       (flat (append (reverse (car lst))  ;; NB
                     (cdr lst))
             rs))))

仍然存在一个争论点，仍然必须转换为尾递归调用：

(list? a) =>
(flat (append (reverse a) d) rs)         ;; NB
=
(define (flaprev       a  d  rs)
  (cond
    ((null? a)       (flat           d rs))
    ((null? (car a)) (flaprev (cdr a) d rs))
    (else            (flaprev (cdr a)
                         (cons (car a) d) rs))))

巧合的是，这显示了一种转换的通用技术：通过将所有嵌套参数提升到同一级别，将每个非尾部嵌套调用转变为平面调用，然后根据其使用方式、预期产生的结果以及要遵循的规则来实现所需的函数语义。

这种“做这个，然后做那个”的方法通过CPS 技术，在评论中提到：

(define (flatten lst)   ;; your definition
  (cond 
    ((null? lst) '())
    ((list? (car lst)) 
      (append
            (flatten (car lst)) 
                   (flatten (cdr lst))))
    (else 
      (cons (car lst) 
                   (flatten (cdr lst))))))
===
(define (flatten lst)         ;; becomes
  (flat lst (lambda (x) x)))

(define (flat lst c)  ;; continuation "c" = "and then
  (cond               ;;                 use the result as"
    ((null? lst)  (c '()))
    ((list? (car lst))
      (flat (cdr lst) (lambda (rd)
           (flat (car lst) (lambda (ra)
               (c (append ra rd)))))))     ;; NB: append (??)
    (else
      (flat (cdr lst) (lambda (rd)
               (c (cons (car lst) rd)))))))

但是那个讨厌的 append 是怎么回事？我们可以用以下方法消除它
与我们在flaprev中使用的技术相同，通过将所有嵌套参数提升到同一级别，为要反向追加的列表添加显式参数：

(define (flatten lst)
  (flat lst '() (lambda (x) x)))
         ;; ^^^__
         ;;      vvv
(define (flat lst d c)
  (cond  ;;      ___vvv
    ((null? lst)  (c d))
    ((list? (car lst))
      (flat (cdr lst) d (lambda (rd)
           (flat (car lst) rd (lambda (ra)
               (c ra))))))
    (else
      (flat (cdr lst) d (lambda (rd)
               (c (cons (car lst) rd)))))))

现在最长延续的长度是输入中最长的子列表，而不是输出列表的长度。