Создание набора мощности в одной функции, без явной рекурсии и с использованием только простейших примитивов в Racket

Question

Примечание: это бонус за домашнее задание, но я потратил слишком много времени на бесполезные попытки. Помощь приветствуется, но я полагаю, что в ней нет необходимости.

Предпосылка: сгенерируйте набор мощности для списка чисел, но без использования каких-либо помощников, явной рекурсии, цикла или функций / констант, кроме cons, first, rest, empty?, empty, else, lambda, и cond, при использовании только одного define на уровне языка Intermediate Student with Lambda. Порядок набора мощности не имеет значения.

То, что я пробовал до сих пор: я обнаружил Y-комбинатор и анонимную рекурсию благодаря этому сообщению (у автора одна и та же конечная цель, но у нас разные подходы, поэтому информация в его сообщении не решает мою проблему), и 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, и я понятия не имею, как преобразовать это в lambda поскольку, насколько мне известно, Y-комбинатор работает только с одним параметром и combineтребуется 2. Возможно, моя логика или подход к этой проблеме ошибочны. У меня ограниченный опыт работы с lambda так что мне тоже может не хватать знаний.

В чем мне нужна помощь: какие-либо предложения относительно следующих шагов, помощь в интеграции combine в powerset, предоставление подсказок / подсказок для правильной логики / подхода или решение было бы очень полезно.

Заранее спасибо!

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

Answer 2

Y-комбинатор работает только с одним параметром, а для комбинирования требуется 2

Любую функцию с несколькими аргументами можно представить как функцию с одним аргументом, возвращающую лямбду, ожидающую следующего аргумента. Этот процесс называется каррированием. Например, если у нас есть

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

мы могли бы назвать это как

(add 2 2)

Достаточно просто. А теперь карри:

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

Для его вызова используется немного другой синтаксис, но основная идея та же:

((add 2) 2)

Вы можете применить ту же концепцию к любой лямбде, если хотите сделать ее подходящей для комбинатора Y.

Answer 3

В лямбда-исчислении все функции являются каррированными унарными функциями.

Это означает

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