在Scheme中实现幂集

Question

在Scheme中实现幂集

3

我正在尝试用两种不同的方式在Scheme中实现幂集函数。一种方法是使用尾递归，我的实现如下：

(define (powerset list)
 (if (null? list) '(())                                    ;; if list is empty, its powerset is a list containing the empty list
  (let ((rest (powerset (cdr list))))                   ;; define "rest" as the result of the recursion over the rest of list
    (append (map (lambda (x) (cons (car list) x)) rest) ;; add the first element of list to the every element of rest (which is a sublist of rest) 
            rest))))                                    ;; and append it to rest itself (as we can either use the current element (car list), or not

这种方法是可行的。

另一种方法是使用foldr，但这是我遇到问题的地方。我的当前实现如下：

(define (powerset-fr list)
 (foldr (lambda (element result)        ;; This procedure gets an element (and a result);
       (if (null? result) ;; if starting with the empty list, there is nothing to "fold over".
           (cons '() (cons element result))
           (foldr (lambda (inner-element inner-result)
                    (append (cons element result) inner-result))
                  '(())
                  result)))
     '()                             ;; The result is initialized to the empty list,
     list))                         ;; and the procedure is being applied for every element in the first list (list1)

这样的做法得到的结果很差。

我将简要说明我迄今为止如何解决这个问题：

foldr运行在给定集合中的每个元素上。对于每个元素，我应该向幂集添加一些新元素。这些应该是哪些元素？针对现有幂集中的每个元素，添加一个新元素，在该幂集中附加列表中的当前元素。

这就是为什么我认为我应该以嵌套方式两次使用foldr-一次遍历给定列表中的所有项目，对于每个项目，我使用foldr遍历“result”（当前幂集）中的所有项目。

我面临的问题是空列表（没有任何内容被添加到幂集中），因此添加了“if”部分（而不仅仅是foldr），但它也不能很好地工作。

我想这就是全部。我感觉接近了，但仍然非常具有挑战性，所以欢迎任何帮助。谢谢！

- avish12

1

将变量和参数命名为“list”、“rest”是一个不好的主意 - 在某些解释器中，这些是内置过程，可能会导致名称冲突。 - Óscar López

1

一个相当常见的命名约定是使用 xs 表示 x 的列表，使用 xss 表示 x 的列表的列表。 - soegaard

“我认为我应该嵌套使用foldr两次”你在那里是完全正确的。 :) - Will Ness

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Óscar López · Accepted Answer

解决方案更简单，不需要使用双重foldr，尝试这样做：

(define (powerset-fr lst)
  (foldr (lambda (e acc)
           (append (map (lambda (x) (cons e x)) 
                        acc) 
                   acc))
         '(())
         lst))

如果你的解释器定义了 append-map 或其等效物，则解决方案会更为简洁 - 结果将以不同顺序呈现，但这并不重要:

(define (powerset-fr lst)
  (foldr (lambda (e acc)
           (append-map (lambda (x) (list x (cons e x)))
                       acc))
         '(())
         lst))

无论哪种方式，它都能按预期工作：

(powerset-fr '(1 2 3))
=> '((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())