嵌套列表的文件夹

Question

问题

好的，我们都知道 foldr 及其在列表上的工作方式。但是在嵌套列表上工作的 foldr 呢？这就是我今天要解决的问题，构建一个名为 nested-foldr 的函数，它采用与 foldr 相同的参数，但也适用于嵌套列表。

例子

由于嵌套列表中可以有尽可能多的列表，下面是一个例子

(nested-foldr + 0 (list 1 (list 5 5 (list 1 3)) (list 10 2) 2))

这个应该return29.

当前解决方案

我还没有很沮丧。我制作了一个名为 my-foldr 的函数，它基本上完成了 foldr 的功能。 “combine”是应用于列表的函数，“base”是基本情况。 “lst”是函数使用的列表。

(define (my-foldr combine base lst)
  (cond [(empty? lst) base]
        [else (combine (first lst) (my-foldr combine base (rest lst)))]))

编辑：我对它和“成员？”的使用有了更多的思考。谓词在这里也应该有用。虽然我不确定如何使用它。

Answer 1

您的解决方案没有考虑到列表中的任何元素都可以是列表本身，我们需要对其进行递归 - 事实上，我们正在处理树, 而不仅仅是列表。它比看起来更棘手，我想不出一种方法来保留 foldr 顺序而不先反转输入。尽管如此，这对我有用：

(define (reverse-tree tree)
  (let loop ((lst tree)
             (acc '()))
    (cond ((null? lst) acc)
          ((not (pair? lst)) lst)
          (else (loop (cdr lst)
                      (cons (car lst)
                            acc))))))

(define (nested-foldr combine base tree)
  (let loop ((lst (reverse-tree tree))
             (acc base))
    (cond ((null? lst) acc)
          ((not (pair? lst)) lst)
          (else (loop (cdr lst)
                      (combine (nested-foldr combine base (car lst))
                               acc))))))

例如：

(nested-foldr + 0 '(1 (5 5 (1 3)) (10 2) 2))
=> 29
(nested-foldr cons '() '(1 (5 5 (1 3)) (10 2) 2))
=> '(1 (5 5 (1 3)) (10 2) 2)

嵌套列表的文件夹

Foldr for nested lists

scheme

nested-lists

racket

问题

例子

当前解决方案