functional-programming - 在 scheme 中转换具有两次递归调用的函数以使其成为尾递归

Question

在我开始之前:是的，这是大学的作业。在我被告知我懒惰和邪恶之前:这部分作业是转换我们已经拥有的两个函数，这个是第 6 个。

(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? ，成长 empty有意义列表;我们正在使用 acc以此目的。你可以在 else 中看到它是如何工作的上面的分支。但是我们应该能够处理嵌套列表。当我们更深入时，我们应该保留嵌套列表的其余元素以供进一步处理。样本列表: (list 1 (list 2 3) 4 5)
直到 (list 2 3)我们已经添加了 1到蓄能器。由于我们不能使用堆栈，我们需要一些其他地方来存储列表的其余元素。而这个地方是 lst参数，其中包含要展平的原始列表的元素。我们可以只是 append lst到其余元素 (cdr (list 2 3))分别是 (list 3) ，然后继续我们在展平时偶然发现的列表的头部，i。 e. (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?和 reverse在 acc 上执行.然后函数返回反向累加器。