在方案中使用两个递归调用转换函数以使其呈尾递归

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),然后继续列表的头部,我们在展平时偶然发现,即(汽车(清单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.然后,函数返回反向累加器.