Génération de Powerset dans une fonction, pas de récursivité explicite, et en utilisant uniquement les primitives les plus simples dans Racket

Question

Remarque: c'est un bonus pour les devoirs, mais j'ai passé beaucoup trop de temps à essayer des choses en vain. L'aide est très appréciée, mais pas nécessaire je suppose.

Prémisse: générer un powerset pour une liste de numéros, mais sans utiliser des aides, récursivité explicite, en boucle, ou des fonctions / constantes autres que cons, first, rest, empty?, empty, else, lambdaet cond, tout en utilisant une seule definesur le niveau de langue Intermediate Student with Lambda. L'ordre de l'ensemble de puissance n'a pas d'importance.

Ce que j'ai essayé jusqu'à présent: j'ai découvert le combinateur Y et la récursivité anonyme grâce à ce post (l'auteur a le même but final mais nous avons des approches différentes, donc les informations contenues dans son post ne résolvent pas mon problème), et le powersetcode dans cette réponse , et avec cela, j'ai écrit ce qui suit:

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

Je teste ce code en exécutant:

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

Ce code s'exécute et produit un résultat correct, mais, comme vous pouvez le voir, je compte toujours sur une fonction d'assistance externe combine, et je n'ai aucune idée de comment le convertir en un lambdacar à ma connaissance, le combinateur Y ne fonctionne qu'avec un seul paramètre et combinebesoins 2. Peut-être que ma logique ou mon approche de ce problème est défectueuse. J'ai une expérience limitée, lambdadonc je pourrais aussi manquer de connaissances.

Ce pour quoi j'ai besoin d'aide: toute suggestion concernant les prochaines étapes, m'aidant combineà m'intégrer powerset, fournissant des conseils / indices pour corriger la logique / approche, ou une solution serait très appréciée.

Merci d'avance!

Answer 1

Je trouve l'astuce ci-dessous plus facile à comprendre que d'utiliser Y. Je pense que c'est en quelque sorte lié à U (que je trouve aussi plus facile à comprendre que Y).

Il est possible que ce ne soit pas suffisant pour répondre à l'exigence de «ne pas être explicitement récursif», même si je pense que c'est le cas.

Si vous avez une fonction qui `` veut '' s'utiliser librement pour qu'elle puisse se répéter, telle que:

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

Ensuite, vous pouvez transformer cela en une fonction qui prend un argument supplémentaire, qu'il appelle:

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

Les /cnoms sont parce que quand j'ai découvert cette astuce, je pensais à l'argument comme une continuation, mais je pense que c'est parce que je ne savais pas ce qu'étaient vraiment les suites.

Et maintenant (avec une définition pour combine), (powerset/c powerset/c '(x y z))va calculer l'ensemble de puissance de (x y z), et il n'y a pas de récursivité explicite.

Eh bien, c'est moche mais c'est facile à réparer en utilisant

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

Ensuite, l'astuce consiste à écrire de combinecette façon également, puis à l'utiliser localement, avec

(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

le combinateur Y ne fonctionne qu'avec un paramètre et combine les besoins 2

Toute fonction multi-argument peut être imaginée comme une fonction à un argument, renvoyant un lambda qui attend le prochain argument. Ce processus est appelé curry. Par exemple, si nous avons

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

nous pourrions l'appeler comme

(add 2 2)

Assez simple. Maintenant, curons-le:

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

L'appeler prend une syntaxe légèrement différente, mais c'est la même idée de base:

((add 2) 2)

Vous pouvez appliquer le même concept à n'importe quel lambda si vous souhaitez l'adapter au combinateur Y.

Answer 3

Dans le calcul lambda, toutes les fonctions sont des fonctions unaires curry.

Ça signifie

(define (combine a r)
  (cond
    [(empty? r)  empty]
    [else (cons (cons a (first r))
                (cons (first r) 
                      (combine a (rest r))))]))

serait écrit comme

(λ (combine)
  (λ (a)
    (λ (r)
      (cond
        [(empty? r) empty]
        [else (cons (cons a (first r))
                    (cons (first r) 
                          ((combine a) (rest r))))]))))

Dans cet esprit, voici la solution:

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