3

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

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

到目前为止我所尝试的： 感谢这篇文章，我发现了 Y-combinator 和匿名递归（作者的最终目标相同，但我们有不同的方法，所以他的帖子中的信息不能解决我的问题），以及这个答案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并且我不知道如何将其转换为 a，lambda因为据我所知，Y-combinator 仅适用于一个参数和combine需求 2. 也许我对这个问题的逻辑或方法有缺陷。我的经验有限，lambda所以我也可能缺少知识。

我需要帮助：关于下一步的任何建议，帮助我combine融入powerset，提供提示/线索以纠正逻辑/方法，或解决方案将不胜感激。

提前致谢！

4

3 回答 3

4

Y-combinator 仅适用于一个参数并且组合需要 2

任何多参数函数都可以想象成一个单参数函数，返回一个等待下一个参数的 lambda。这个过程称为柯里化。例如，如果我们有

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

我们可以这样称呼它

(add 2 2)

很简单。现在让我们咖喱它：

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

调用它的语法略有不同，但基本思想相同：

((add 2) 2)

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

于 2020-11-19T03:44:23.597 回答
2

在 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)))])))))
于 2020-11-30T15:59:30.993 回答
1

我发现下面的技巧比使用 Y 更容易理解。我认为它与 U 有点相关（我也发现它比 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>)))
于 2020-11-19T16:37:30.393 回答