Powerset d'une liste utilisant des fonctions de liste abstraites

Question

Est-il possible de faire fonctionner une raquette pour renvoyer l'ensemble de puissance d'une liste donnée ?

---

Contraintes-

1. sans récursivité explicite
2. utiliser des fonctions de liste abstraite
3. code contenu dans 2 lignes (exigence réelle)

---

Par exemple: (powerset '(1 2))

'((1 2) (1) (2) ())

dans n'importe quel ordre.

L'autre question que j'ai trouvée utilise toujours la récursivité explicite.

---

Mon workflow:

1. Prenant (powerset '(a b c))comme exemple,
2. Obtenez d'abord une liste de nombres entiers jusqu'à (expt 2 (length list)) ;'(0 1 2 3 4 5 6 7)
3. Convertissez-les dans leur forme binaire respective 2->(0,1,0). Alors on obtient'((0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1))
4. map '(1 2 3) à la liste des binaires. Par exemple:2->'(0,1,0)->'((0,a) (1,b) (0,c))
5. filtrer la liste résultante avec un lambda tel que nous conservons les éléments avec 1, comme '((1,b)).
6. Extraire le jeu de pouvoirs

---

Problème avec mon approche

Il ne suit pas la contrainte de la question étant en 1 ligne (en plus de l'en-tête de la fonction).

(define (powerset list)
  ( ... )) ;; ie the code is contained in 2 lines of 80 characters

---

J'avais cette question dans ma mission comme question bonus mais je n'ai pas pu le faire.

1. Que sont les fonctions de liste abstraite?

• Fonctions comme foldl, foldretmap

1. Mon bonus comprenait 3 sous-parties

• La partie 1 demandait simplement de faire cette fonction de la manière que je voulais. J'ai donc utilisé la récursivité pour le faire
• La partie 2 est la partie sur laquelle j'ai posé la question. Celui-ci était particulièrement difficile car il y avait une contrainte supplémentaire du code d'être à moins de 2 lignes
• La troisième partie était censée être la plus difficile.

N'écrivez aucune fonction d'assistance et n'utilisez aucune récursivité explicite (c'est-à-dire que votre fonction ne peut pas s'appeler par son nom). N'utilisez aucune fonction de liste abstraite. En fait, utilisez uniquement la liste suivante des fonctions, des constantes et Racket formes spéciales: cons, first, rest, empty?, empty, lambdaet cond.

Cependant, chose amusante, j'ai étudié Y-combinatoret j'ai pu résoudre celui-ci (après 6 heures de codage).

Answer 1

Pour répondre à votre bonus partie 2:

(define (pws l) 
  (foldr (lambda (e a) (append (map (lambda (x) (cons e x)) a) a)) '(()) l))

Deux lignes, moins de 80 caractères chacune, première ligne réservée pour le define(donc, une ligne).

Si ce appendn'est pas autorisé, nous transformons également la append ... mapcombinaison en un foldr:

(define (pws-fr l) 
  (foldr (lambda (e a)
           (foldr (lambda (x r)
                    (cons (cons e x) r))
                  a a))
         '(()) l))

ou, raccourci,

(define (pws-fr-1 l) 
  (foldr (lambda (e a) (foldr (lambda (x r) (cons (cons e x) r)) a a)) '(()) l))

(avec précisément 80 caractères dans sa deuxième ligne).

Une autre façon de coder ceci est le append-mapcode basé sur le code (le deuxième extrait de code) de cette réponse qui, lorsqu'il est recodé avec foldrseulement, devient

(define (pws-am-fr l) 
  (foldr (lambda (e a)
           (foldr (lambda (x r)
                    (cons x (cons (cons e x) r)))
                  '() a))
         '(()) l))

ou raccourci,

(define (pws-am-fr1 l) (foldr (lambda (e a)
   (foldr (lambda (x r) (cons x (cons (cons e x) r))) '() a)) '(()) l))

qui pourraient ou non répondre exactement à vos exigences.