在 lisp 中反转带有子列表和原子的列表

Question

我是函数式编程的新手，正在尝试用 lisp 反转列表。列表由子列表和原子组成。函数 (reverse-tree '((1 2) 5 6 (3))) 应该 return ((3) 6 5 (2 1))。这是我的功能：

(define (reverse-tree s)
    ;; giving problem with an atom 
  (if (not(list? s)) ( reverse-tree s) (reverse (map reverse s)))

  )

当我执行 (reverse-tree '((1 2) (3))) => ((3) (2 1)) 时它起作用了。但是当我 (reverse-tree '((1 2) 5 6 (3))) 时它崩溃了。我得到的错误是 reverse: contract violation expected: list?

我仅限于使用：reverse, map, if, cond, list? null?个函数。

编辑，有人将此问题标记为重复，但此问题中有一个限制，与其他问题不相似。我不能使用cons、car、cdr、append。有什么建议吗？

Answer 1

把问题分块考虑。首先，如果给函数一个列表作为参数，则需要反转该列表。这很简单，例如：

(define (reverse-tree tree)
  (if (list? tree)
      (reverse tree)
      ...))

但是你还需要把里面的所有子列表和里面的所有子列表都反转等等。由于这正是我们的 reverse-tree 所做的，我们应该使用 map 将其应用于反转列表中的所有元素（实际上，在反转列表之前或之后使用 map 并不重要列表):

(define (reverse-tree tree)
  (if (list? tree)
      (map reverse-tree (reverse tree))
      ...))

但是如果输入是 ((1 2) 3 4 (5 6))，map 也会在原子 3 和 4 上调用 reverse-tree。反转它们没有任何意义，所以我们可以 return 它们：

(define (reverse-tree tree)
  (if (list? tree) 
      (map reverse-tree (reverse tree))
      tree))

现在它应该可以工作了：

(reverse-tree '((1 2) 3 4 (5 6)))
;=> ((6 5) 4 3 (2 1))
(reverse-tree '((1 2) 3 4 (5 6 (7 8))))
;=> (((8 7) 6 5) 4 3 (2 1))

在 lisp 中反转带有子列表和原子的列表

Reversing list with sublists and atoms in lisp

lisp

scheme