如何反转清单？

Question

Scheme中列表的功能是什么？它需要能够处理嵌套列表.

因此,如果你做了类似于(reverse '(a (b c d) e))你(e (b c d) a)的输出.

我该如何处理这个问题？我不只是在寻找答案,而是能帮助我学习的东西.

Answer 1

(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 '()))

这使用累加器变量来反转列表,将第一个元素从传入列表中取出并将其传递到累加器的前面.它隐藏了累加器获取功能并且只暴露了获取列表的函数,因此调用者不必传入空列表.这就是我有反向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)

Answer 2

(define (reverse1 l)
  (if (null? l)
     nil
     (append (reverse1 (cdr l)) (list (car l)))
  )
)

说明:

规则:
1.如果列表为空,则反向列表也为空
2.否则在列表的反向尾部后面添加列表的第一个元素

以这种方式看看这段代码:

reverse1是函数的名称,l是参数,
如果list为空,则reverse也为空,否则使用(cdr l)调用reverse1函数,这是列表的尾部,并将其作为列表附加到第一个alement(car l)

在你的例子中(伪鳕鱼):

1st iteration 
l=>(a (bcd)e)
car l => a
cdr l => (bcd)e
list(car l) =>(a)
------------------
reverse( cdr l)"+"(a)
------------------
2nd iteration
l=>((bcd)e)
car l => (bcd)
cdr l =>e
list(car l)=>(bcd)
--------------------
reverse(cdr l)"+"((bcd))+(a)
-----------------------
3rd iteration
l=>e
car l=> e
cdr l => nil
list (car l) =>(e)
-------------------------
(e (bcd)a)