在一个函数中生成幂集，无需显式递归，并且仅在Racket中使用最简单的原语 [英] Generating powerset in one function, no explicit recursion, and using only simplest primitives in Racket

问题描述

注意:这是功课的奖励，但我花了很长时间尝试这些事情无济于事.非常感谢您的帮助，但我认为这不是必需的.

前提: 为数字列表生成幂集，但不使用任何辅助函数，显式递归，循环或cons，first，rest，empty?，empty，else， lambda和cond，而在语言级别Intermediate Student with Lambda上仅使用一个define.幂集的顺序无关紧要.

到目前为止，我已经尝试过: 感谢这篇文章，我发现了Y-combinator和匿名递归. (作者具有相同的最终目标，但我们使用的方法不同，因此他帖子中的信息不能解决我的问题)，以及解决方案

我发现下面的技巧比使用Y更容易理解.我认为它与U有关(我也比Y更容易理解). /p>

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

如果您具有一些想要"自由使用的功能，以便可以递归使用，例如:

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

Note: this is a bonus for homework, but I have spent way too long on trying things to no avail. Help is much appreciated, but not necessary I suppose.

Premise: generate a powerset for a list of numbers, but without using any helpers, explicit recursion, looping, or functions/constants other than cons, first, rest, empty?, empty, else, lambda, and cond, while using only one define on the language level Intermediate Student with Lambda. The order of the powerset does not matter.

What I've tried so far: I have discovered the Y-combinator and anonymous recursion thanks to 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, and with that I have written the following:

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

I'm testing this code by running:

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

This code runs and produces a correct result, but, as you can see, I still rely on an external helper function, combine, and I have no idea how to convert that into a lambda since to my knowledge, the Y-combinator only works with one parameter and combine needs 2. Perhaps my logic or approach to this problem is flawed. I have limited experience with lambda so I could be missing knowledge as well.

What I need help with: any suggestions as to next steps, helping me intergrate combine into powerset, providing hints/clues to correct logic/approach, or a solution would be much appreciated.

Thanks in advance!

解决方案

I find the trick below easier to understand than using Y. I think it's sort of related to U (which I also find easier to understand than Y).

It's possible that this isn't enough to meet the requirement of 'not being explicitly recursive', although I think it is.

If you have some function which 'wants' to use itself freely so it can recurse, such as:

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

Then you can turn that into a function which takes an additional argument, which it calls:

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

The /c names are because when I discovered this trick I was thinking about the argument as a continuation, but I think that's because I didn't know what continuations were really.

And now (with a definition for combine), (powerset/c powerset/c '(x y z)) will compute the power set of (x y z), and there is no explicit recursion.

Well, that's ugly but this is easy to fix using

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

Then the trick is to write combine this way as well, and then use it locally, with

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

这篇关于在一个函数中生成幂集，无需显式递归，并且仅在Racket中使用最简单的原语的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！