方案:以原始顺序重建列表的迭代过程? [英] Scheme: Iterative process to reconstruct a list in original order?

问题描述

我的问题是:如何编写一个利用尾调用的过程，该过程不能以相反的顺序构造一个列表.为了说明我的意思，这是一个非常简单的过程的示例，该过程是迭代的，并且会创建列表的副本:

My question is: how to write a procedure that utilises tailcall, and that constructs a list not in the reverse order. To show what I mean, here is an example of a very simple procedure that is iterative, and that creates a copy of a list:

(define (copy-list ls)
    (define (iter cp-ls rest-ls)
      (if (null? rest-ls)
          cp-ls
          (iter (cons (car rest-ls) cp-ls) (cdr rest-ls))))
    (iter '() ls))

问题在于，由于将元素 cons 组合在一起的迭代顺序，返回的列表最终会颠倒过来.是的，您可以通过执行(反向cp-list)而不是仅仅在 if 块中使用 cp-list 来解决此问题，但是问题是 reverse 是一个递归过程.利用此过程将取消尾调用的优势，即堆栈大小随输入大小线性增长.

The problem is that, due to the iterative order in which the elements are consed together, the returned list ends up reversed. Yes, you could easily solve this by doing (reverse cp-list) instead of just cp-list in the if-block, but the problem with this is that reverse is a recursive process. Utilising this procedure will nullify the tailcall advantage, which is that the stack size grows linearly with the input size.

因此，基本上，如何编写像上述程序那样使用任何递归过程以正确顺序不返回列表的程序?

So, basically, how to write a procedure like the one mentioned that returns the list in correct order without utilising any sort of recursive processes?

谢谢

推荐答案

(map (lambda(x) x) l)

将复制列表 l ，并且不会递归编写.

will make a copy of the list l and it's not recursivelly written.

(let ((l '(1 2 3 4)))
  ((fold-right (lambda (e acc)
                 (lambda (x) (cons x (acc e))))
               (lambda (x) (list x))
               (cdr l))
   (car l)))

是另一种无需递归但使用monoid复制列表的形式.

is another form to copy a list without recursion, but using a monoid.

其他:

(let ((l '(1 2 3 4)))
  (car ((fold-right (lambda (e acc)
                      (lambda (x) (acc (append x (list e)))))
                    (lambda (x) (list x))
                    (cdr l))
        (list (car l)))))

其他:

(let ((l '(1 2 3 4)))
  (cdr ((fold-left (lambda (acc e)
                     (lambda (x) (cons x (acc e))))
                   (lambda (x) (list x))
                   l)
        'first)))

其他(由 Will 建议):

(let ((l '(1 2 3 4)))
  ((fold-right (lambda (e acc)
                 (lambda (k) (k (acc (lambda (es) (cons e es))))))
               (lambda (z) (z (list))) l)
   (lambda (es) es)))

还有很多其他方法可以复制列表.通常，要进行复制，您需要直接或间接致电 cons .

There are lots of other ways to copy a list. In general, to make a copy, you need to call, either directly or indirectly, cons.

如评论中所述，并非所有这些方式都使用迭代过程.

As mentioned in the comments, not all these ways use an iterative process.

这篇关于方案:以原始顺序重建列表的迭代过程?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！