recursion - 如何反转列表?

标签 recursion scheme reverse

Scheme中反转列表的功能是什么?
它需要能够处理嵌套列表。因此,如果您执行 (reverse '(a (b c d) e)) 之类的操作你会得到(e (b c d) a)作为输出。
我应该如何解决这个问题?我不只是在寻找答案,而是在寻找可以帮助我学习的东西。

最佳答案

(define (my-reverse ls)
  (define (my-reverse-2 ls acc)
    (if (null? ls)
      acc
      (my-reverse-2 (cdr ls) (cons (car ls) acc))))
  (my-reverse-2 ls '()))

这使用一个累加器变量来反转列表,从传入列表中取出第一个元素并将其放在累加器的前面。它隐藏了累加器获取函数,只公开了获取列表的函数,因此调用者不必传入空列表。这就是为什么我有 my-reverse-2。
(my-reverse-2 '(a (b c d) e) '()); will call
(my-reverse-2 '((b c d) e)  '(a)); which will call
(my-reverse-2 '(e)  '((b c d) a)); which will call
(my-reverse-2 '() '(e (b c d) a)); which will return
'(e (b c d) a)

因为 my-reverse-2 中的最后一个函数调用调用my-reverse-2 ,返回值直接传递(第一次调用的返回值就是第二次调用的返回值,以此类推)my-reverse-2是尾部优化的,这意味着它不会用完堆栈上的空间。因此,只要您愿意,就可以使用列表来调用它。

如果您希望它应用于嵌套列表,请使用以下内容:
(define (deep-reverse ls)
  (define (deep-reverse-2 ls acc)
    (if (null? ls)
        acc
        (if (list? (car ls))
            (deep-reverse-2 (cdr ls) (cons (deep-reverse (car ls)) acc))
            (deep-reverse-2 (cdr ls) (cons (car ls) acc)))))
  (deep-reverse-2 ls '()))

这会在将元素添加到列表之前检查元素是否为列表,如果是,则首先将其反转。
由于它调用自身来反转内部列表,它可以处理任意嵌套。
(deep-reverse '(a (b c d) e)) -> '(e (d c b) a)尽管存在嵌套列表,但它是按字母倒序排列的。
它评估如下:
(deep-reverse-2 '(a (b c d) e) '()); Which calls
(deep-reverse-2 '((b c d) e)  '(a))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(b c d) '()) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(c d)  '(b)) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(d)  '(c b)) '(a)))
(deep-reverse-2 '(e) (cons '(d c b) '(a)))
(deep-reverse-2 '(e)  '((d c b) a))
(deep-reverse-2 '() '(e (d c b) a))
'(e (d c b) a)

关于recursion - 如何反转列表?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4092113/

相关文章:

loops - for/continue in scheme/lisp

PHP 反向 Preg_match

c++ - 递归函数如何对二叉树进行操作?

haskell - 删除列表中满足条件的第一个值

c++ - 为什么理解这个递归示例如此难以凭直觉?

c++ - 我试图在C++中编码递归斐波那契序列,但是当我编译时遇到错误

linux - 如何在 Ubuntu 8.10 中为 6.001 设置 MIT Scheme

scheme - Scheme中可变参数map函数的实现

python - 如何仅将文件中每行的最后一部分用于python?

iphone - 如何颠倒NSMutableData的顺序