Scheme中列表的递归 - 避免过早终止 [英] Recursion on a list in Scheme - avoid premature termination

问题描述

我正在解决 HTDP 书中的一个问题，您必须创建一个函数来查找列表的所有排列.这本书给出了 main 函数，问题要求你创建一个辅助函数，该函数将在列表中的任何地方插入一个元素.名为 insert_everywhere 的辅助函数只提供了 2 个参数.

I was doing a problem from the HTDP book where you have to create a function that finds all the permutations for the list. The book gives the main function, and the question asks for you to create the helper function that would insert an element everywhere in the list. The helper function, called insert_everywhere, is only given 2 parameters.

无论我多么努力，我似乎​​都无法仅使用两个参数来创建此函数.

No matter how hard I try, I can't seem to create this function using only two parameters.

这是我的代码:

(define (insert_everywhere elt lst)
  (cond
    [(empty? lst) empty]
    [else (append (cons elt lst) 
                  (cons (first lst) (insert_everywhere elt (rest lst))))]))

我想要的 (insert_everywhere 'a (list 1 2 3)) 输出是 (list 'a 1 2 3 1 'a 2 3 1 2 'a 3 1 2 3 'a)，但我的列表一直在终止.

My desired output for (insert_everywhere 'a (list 1 2 3)) is (list 'a 1 2 3 1 'a 2 3 1 2 'a 3 1 2 3 'a), but instead my list keeps terminating.

我已经能够使用第三个参数位置"创建此函数，我在该参数上对该参数进行递归，但这会破坏我的主函数.有没有办法创建这个只有两个参数的辅助函数?谢谢！

I've been able to create this function using a 3rd parameter "position" where I do recursion on that parameter, but that botches my main function. Is there anyway to create this helper function with only two parameters? Thanks!

推荐答案

如何为辅助函数创建辅助函数?

How about creating a helper function to the helper function?

(define (insert_everywhere elt lst)
    (define (insert_everywhere_aux elt lst)
      (cons (cons elt lst)
            (if (empty? lst)
                empty
                (map (lambda (x) (cons (first lst) x))
                     (insert_everywhere_aux elt (rest lst))))))
    (apply append (insert_everywhere_aux elt lst)))

我们需要将我们的子列表分开，以便每个子列表都可以单独添加前缀.如果我们过早地追加所有，我们就会失去边界.所以我们最后只追加一次:

We need our sublists kept separate, so that each one can be prefixed separately. If we'd append all prematurely, we'd lose the boundaries. So we append only once, in the very end:

insert a (list 1 2 3) =                             ; step-by-step illustration:
                                            ((a))   ; the base case;
                              ((a/ 3)/    (3/ a))   ; '/' signifies the consing
                 ((a/ 2 3)/  (2/ a 3)   (2/ 3 a))
   ((a/ 1 2 3)/ (1/ a 2 3) (1/ 2 a 3) (1/ 2 3 a))
   ( a  1 2 3    1  a 2 3   1  2 a 3   1  2 3 a )   ; the result

测试:

(insert_everywhere 'a (list 1 2 3))
;Value 19: (a 1 2 3 1 a 2 3 1 2 a 3 1 2 3 a)

顺便说一下，这个内部函数是尾递归取模缺点，或多或少，如图所示.这表明应该可以将其转换为迭代形式.Joshua Taylor 展示了另一种方式，使用 revappend.预先反转列表简化了他的解决方案中的流程(现在对应于直接构建插图中的结果行，从右到左，而不是我的版本中的按列"):

By the way this internal function is tail recursive modulo cons, more or less, as also seen in the illustration. This suggests it should be possible to convert it into an iterative form. Joshua Taylor shows another way, using revappend. Reversing the list upfront simplifies the flow in his solution (which now corresponds to building directly the result row in the illustration, from right to left, instead of "by columns" in my version):

(define (insert_everywhere elt lst)
  (let g ((rev (reverse lst)) 
          (q   '())
          (res '()))
    (if (null? rev) 
      (cons elt (append q res))
      (g (cdr rev) 
         (cons (car rev) q) 
         (revappend rev (cons elt (append q res)))))))

这篇关于Scheme中列表的递归 - 避免过早终止的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！