时间戳

首页 > 解决方案 > 在一个函数中生成幂集，没有显式递归，并且只使用 Racket 中最简单的原语

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

问题描述

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

前提： 为数字列表生成一个幂集，但不使用任何帮助器、显式递归、循环或除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，提供提示/线索以纠正逻辑/方法，或解决方案将不胜感激。

提前致谢！

标签： lambdaschemelispracketanonymous-recursion

解决方案

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。

推荐阅读