scheme - 使用抽象列表函数的列表幂集

Question

是否可以让 Racket 函数返回给定列表的幂集？

---

约束-

1. 没有显式递归
2. 使用抽象列表函数
3. 代码包含两行(实际要求)

---

例如: (powerset '(1 2))

'((1 2) (1) (2) ())

以任意顺序。

其他question我发现仍然使用显式递归。

---

我的工作流程:

1. 以(powerset '(a b c))为例，
2. 首先获取直到 (expt 2 (length list)) ;'(0 1 2 3 4 5 6 7) 的整数列表
3. 将它们转换为各自的二进制形式2->(0,1,0)。所以我们得到 '((0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1 ,0,1), (1,1,0), (1,1,1))
4. 将 '(1 2 3) 映射到二进制文件列表。例如:2->'(0,1,0)->'((0,a) (1,b) (0,c))
5. 使用 lambda 过滤结果列表，以便保留值为 1 的元素，例如 '((1,b))。
6. 提取幂集

---

我的方法有问题

它不遵循问题在 1 行中的约束(除了函数头)。

(define (powerset list)
  ( ... )) ;; ie the code is contained in 2 lines of 80 characters

---

我在作业中将这个问题作为奖励问题，但我无法做到。

1. 什么是抽象列表函数？

• 诸如 foldl、foldr 和 map 的函数

我的奖金包括 3 个子部分

• 第 1 部分要求以我想要的任何方式简单地实现此功能。所以我使用递归来做到这一点
• 第 2 部分是我提出问题的部分。这一项特别困难，因为有一个额外的限制，即代码必须在 2 行内
• 第 3 部分应该是最难的。

Do not write any helper functions, and do not use any explicit recursion (i.e., your function cannot call itself by name). Do not use any abstract list functions. In fact, use only the following list of Racket functions, constants and special forms: cons, first, rest, empty?, empty, lambda, and cond.

但是，有趣的是，我研究了 Y-combinator 并能够解决这个问题(经过 6 小时的编码)。

Answer 1

回答您的奖金第 2 部分:

(define (pws l) 
  (foldr (lambda (e a) (append (map (lambda (x) (cons e x)) a) a)) '(()) l))

两行，每行少于 80 个字符，第一行保留用于 define(因此，一行 行)。

如果不允许 append，那么我们也将 append ... map 组合转换为 foldr:

(define (pws-fr l) 
  (foldr (lambda (e a)
           (foldr (lambda (x r)
                    (cons (cons e x) r))
                  a a))
         '(()) l))

或者，缩短，

(define (pws-fr-1 l) 
  (foldr (lambda (e a) (foldr (lambda (x r) (cons (cons e x) r)) a a)) '(()) l))

(第二行正好有 80 个字符)。

另一种编码方法是 this answer 中基于 append-map 的代码(第二个片段)。仅使用 foldr 重新编码时，变为

(define (pws-am-fr l) 
  (foldr (lambda (e a)
           (foldr (lambda (x r)
                    (cons x (cons (cons e x) r)))
                  '() a))
         '(()) l))

或缩短，

(define (pws-am-fr1 l) (foldr (lambda (e a)
   (foldr (lambda (x r) (cons x (cons (cons e x) r))) '() a)) '(()) l))

这可能会也可能不会完全满足您的要求。