list - 方案 - 列表的子集

Question

我需要编写一个函数来生成给定列表的所有子集。我有一个使用 map 的递归版本，但作为奖励，我被要求创建一个函数，该函数在不使用显式递归、本地或任何抽象列表函数的情况下执行此操作。我可以使用 cons , empty? , empty , first , rest和 cond .我正处于崩溃的边缘 - 有什么建议吗？我应该为每个需要执行的递归使用 lambda 语句吗？

Answer 1

我非常怀疑您的教授是否要求您创建或使用 Y-Combinator 来解决这个问题，但如果您想尝试这样做，这里有一些可能会有所帮助的代码。通俗地说，y 组合器是一种无需定义任何东西即可使用 lambda 演算的威力来创建函数的方法。如果您有一个工作定义(您提到过您这样做)，那么将其转换为 lambda 并不太难。我将通过这些步骤并尽我最大的努力在下面解释它，但这是一个非常困难的概念，也是函数式编程中最“令人兴奋”的想法之一。

以下是一个通常定义的函数，它将返回给定列表的长度:

;; mylength : [listof Any] -> Number
;; returns the length of xs
(define (mylength xs)
  (if (empty? xs)
      0
      (+ 1 (mylength (rest xs)))))

现在，要开始走出定义和显式递归的标准领域，让我们制作 mylength一个 lambda 表达式，给定一个能够确定列表长度的函数，返回给定列表的长度， ys .

;; ys is a [Listof Any]
;; mylength is a function that returns the length of a list
(λ (ys)
  (cond [(empty? ys) 0]
        [else (+ 1 (mylength (rest ys)))]))

这段代码的问题是我们不想拥有 mylength在我们的代码中。为了让您以正确的方式思考，请记住这个 lambda 函数的全部意义在于返回给定列表的长度。现在这看起来像是一个神秘的消息，但你会在几行中看到我的意思。

无论如何，仅使用 lambda 表达式表达此定义的下一步是使长度函数成为 lambda 函数的参数，如下所示:

;; ys is a [Listof Any]
(λ (len ys)
  ;; if ys is empty, return 0.
  (if (empty? ys) 0
      ;; otherwise, call len again, passing len itself as it's 1st argument.
      (+ 1 (len len (rest ys)))))

在那里的代码末尾看到这一行可能会令人困惑:
(+ 1 (len len (rest ys)))))毕竟 len是一个只接受一个列表并返回它的长度的函数，对吗？ 错误的。 我们没有接受列表并返回其长度的函数——我们不能使用像第一个 mylength 这样的函数。这里提到的功能。我们需要一些其他函数，其目的是返回列表的长度。如果你还记得我“神秘地”说了几行的话，

remember that the entire point of this lambda function is to return the length of a given list

所以，如果这个 lambda 函数返回给定列表的长度，而我们需要的函数返回给定列表的长度......哇。你在想我在想什么吗？

((λ (len ys) (if (empty? ys) 0 
                  (+ 1 (len len (rest ys)))))
  (λ (len xs) (if (empty? xs) 0
                  (+ 1 (len len (rest xs))))) '(your list here))

“什么!？”你可能在想——“你能做到!？”

我的 friend ，答案是肯定的。是的你可以。如果您迷路了，请认真、认真、仔细地查看上面的代码。让我们调用外部 lambda 函数 func 1 ，以及内部 lambda 函数 func 2 . func 1是我们之前写的同一个函数。那部分是有道理的，对吧？ func 1需要一些其他功能， len ，以及一个列表， ys ，并尝试返回 ys 的长度.自 len的目的在 func 1与 func 1 的目的相同有它自己，我们可以通过本质上是 func 1如 len外部 lambda 的参数。

为了更好地理解它，让我们传入列表 '(1)进入我们新的、奇怪的、lambda 怪物:

第一步:
(empty? '(1)) -> FALSE
外部 lambda 确定 '(1)不为空，因此它评估下一步。

`(+ 1 (len len (rest '(1))))
(rest '(1))评估为 empty :
(+ 1 (len len empty))
并且 len 等于
(λ (len xs) (if (empty? xs) 0
(+ 1 (len len (rest xs))))) ，所以以上扩展为:

((λ (len ys) (if (empty? ys) 0 
                  (+ 1 (len len (rest ys)))))
  (λ (len xs) (if (empty? xs) 0
                  (+ 1 (len len xs)))) empty)

然后 empty作为 ys 被插入外部 lambda ，并评估第一个条件语句:
(empty? ys) (empty? empty) -> TRUE
所以 (len len empty)来电返回 0 .现在进入下一步:
(+ 1 0)', which evaluates to 1 , which is the length of the list '(1)`。

这是一个很难理解的概念，我认为我在解释这个概念方面做得并不好，因为我确实帮助您完成了识别它的必要步骤。如果您对 Y-Combinator 的工作原理有了这种理解，那么我就会给我留下深刻的印象——您理解我的杂乱无章的能力，以及我解释这样一个令人困惑的概念的能力。

 1. (empty? '(1)) -> FALSE
 2. (+ 1 (len len (rest ys)))

((λ (len ys) (if (empty? '(1)) 0 
                  (+ 1 (len len (rest ys)))))
  (λ (len xs) (if (empty? xs) 0
                  (+ 1 (len len (rest xs))))) '(your list here))