在一个函数中生成幂集，没有显式递归，并且只使用Racket中最简单的基元

Question

注意：这是家庭作业的奖励，但我花了太长时间尝试，但都无济于事。我们非常感谢你的帮助，但我想这不是必须的。

前提：为数字列表生成幂集，但不使用除cons、first、rest、empty?、empty、else、lambda和cond之外的任何辅助对象、显式递归、循环或函数/常量，同时在语言级别Intermediate Student with Lambda上仅使用一个define。电源组的顺序无关紧要。

到目前为止我所尝试的：由于这篇文章，我发现了Y组合子和匿名递归(作者有相同的最终目标，但我们有不同的方法，所以他文章中的信息并不能解决我的问题(，以及这个答案中的powerset代码，因此我写了以下内容：

(define (powerset aL)
(((lambda (X)
((lambda (proc)
(proc proc))
(lambda (proc)
(X (lambda (arg)
((proc proc) arg))))))
(lambda (subset)
(lambda (lst)
(cond
[(empty? lst) (list empty)]
[else (combine (first aL) (powerset (rest aL)))])))) aL)
(define (combine a r)
(cond
[(empty? r)  empty]
[else (cons (cons a (first r)) (cons (first r) (combine a (rest r))))]))

我正在通过运行来测试此代码

(check-expect (powerset '(1 2 3)) 
(list '(1 2 3) '(2 3) '(1 3) '(3) '(1 2) '(2) '(1) '()))

这段代码运行并产生正确的结果，但是，正如你所看到的，我仍然依赖于一个外部辅助函数combine，我不知道如何将其转换为lambda，因为据我所知，Y组合子只使用一个参数，而combine需要2。也许我处理这个问题的逻辑或方法有缺陷。我对lambda的经验有限，所以我可能也会错过知识。

我需要的帮助：关于下一步的任何建议，帮助我将combine集成到powerset中，为正确的逻辑/方法或解决方案提供提示/线索，都将不胜感激。

提前感谢！

Answer 1

Y组合子只使用一个参数，组合需要2个

任何多参数函数都可以想象成一个单参数函数，返回一个等待下一个参数的lambda。这个过程叫做咖喱。例如，如果我们有

(define add (x y)
(+ x y))

我们可以称之为

(add 2 2)

很简单。现在让我们来试试：

(define (add x)
(lambda (y)
(+ x y)))

调用它需要稍微不同的语法，但它的基本思想是相同的：

((add 2) 2)

如果您希望使lambda适用于Y组合子，则可以将相同的概念应用于任何lambda。

Answer 2

在lambda演算中，所有函数都是curried一元函数。

这意味着

(define (combine a r)
(cond
[(empty? r)  empty]
[else (cons (cons a (first r))
(cons (first r) 
(combine a (rest r))))]))

将被写为

(λ (combine)
(λ (a)
(λ (r)
(cond
[(empty? r) empty]
[else (cons (cons a (first r))
(cons (first r) 
((combine a) (rest r))))]))))

考虑到这一点，以下是解决方案：

(define powerset
((λ (y)
((λ (f) (y (λ (x) ((f f) x))))
(λ (f) (y (λ (x) ((f f) x))))))

(λ (ps)
(λ (set)
(cond
[(empty? set) (cons empty empty)]
[else ((((λ (y)
((λ (f) (y (λ (x) ((f f) x))))
(λ (f) (y (λ (x) ((f f) x))))))

(λ (combine)
(λ (a)
(λ (r)
(cond
[(empty? r) empty]
[else (cons (cons a (first r))
(cons (first r) 
((combine a) (rest r))))])))))
(first set))
(ps (rest set)))])))))

Answer 3

我发现下面的技巧比使用Y更容易理解。

这可能不足以满足"不显式递归"的要求，尽管我认为是这样

如果你有一些函数"想"自由使用它自己，这样它就可以递归，比如：

(define powerset
(λ (set)
(cond [(empty? set)
(list empty)]
[else
(combine (first set)
(powerset (rest set)))])))

然后你可以把它变成一个函数，它需要一个额外的参数，它调用这个参数：

(define powerset/c
(λ (ps/c set)
(cond [(empty? set)
(list empty)]
[else
(combine (first set)
(ps/c ps/c (rest set)))])))

/c的名字是因为当我发现这个技巧时，我认为这个论点是一个延续，但我认为这是因为我不知道延续到底是什么。

现在(有了combine的定义(，(powerset/c powerset/c '(x y z))将计算(x y z)的幂集，并且没有显式递归。

嗯，这很难看，但使用很容易修复

(define powerset
(λ (set)
((λ (powerset/c)
(powerset/c powerset/c set))
(λ (ps/c set)
(cond [(empty? set)
(list empty)]
[else
(combine (first set)
(ps/c ps/c (rest set)))])))))

然后技巧是同样以这种方式写入combine，然后使用在本地使用它

(define powerset
(λ (set)
((λ (combine)
((λ (powerset/c)
(powerset/c powerset/c set))
(λ (ps/c set)
(cond [(empty? set)
(list empty)]
[else
(combine (first set)
(ps/c ps/c (rest set)))]))))
<combine defn here>)))