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

Question

注：这是功课的加分项，但我试了很久都无济于事。非常感谢帮助，但我认为没有必要。

前提： 为数字列表生成幂集，但不使用任何助手、显式递归、循环或 functions/constants 除了 cons、first、rest、empty?、empty、else、lambda 和 cond，而在语言级别 Intermediate Student with Lambda 上只使用一个 define。 powerset 的顺序无关紧要。

到目前为止我尝试过的： 由于 this post (author has the same end goal but we have different approaches, so the information in his post does not solve my problem), and the powerset code in this answer，我发现了 Y 组合子和匿名递归，并且我写了以下内容：

(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，提供 hints/clues正确 logic/approach，否则将不胜感激。

提前致谢！

Answer 1

the Y-combinator only works with one parameter and combine needs 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

我发现下面的技巧比使用 Y 更容易理解。我认为它与 U 有点相关（我也发现它比 Y 更容易理解）。

这可能不足以满足'not being explicitly recursive'的要求，虽然我认为是。

如果你有一些函数 'wants' 可以自由使用它自己，这样它就可以递归，例如：

(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>)))

Answer 3

在 lambda 演算中，所有函数都是柯里化一元函数。

这意味着

(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)))])))))

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

Generating powerset in one function, no explicit recursion, and using only simplest primitives in Racket

lisp

lambda

scheme

racket

anonymous-recursion