Powerset de una lista usando funciones de lista abstracta

Question

¿Es posible hacer que una función de raqueta devuelva powerset de una lista dada ?

---

Restricciones

1. sin recursividad explícita
2. usar funciones de lista abstracta
3. código contenido en 2 líneas (requisito real)

---

Por ejemplo: (powerset '(1 2))

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

en cualquier orden.

La otra pregunta que encontré todavía usa la recursividad explícita.

---

Mi flujo de trabajo:

1. Tomando (powerset '(a b c))como ejemplo,
2. Primero obtenga una lista de números enteros hasta (expt 2 (length list)) ;'(0 1 2 3 4 5 6 7)
3. Conviértelos en su respectiva forma binaria 2->(0,1,0). Entonces obtenemos'((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) a la lista de binarios. Por ejemplo:2->'(0,1,0)->'((0,a) (1,b) (0,c))
5. filtrar la lista resultante con una lambda de modo que mantengamos los elementos con 1, como '((1,b)).
6. Extrae el powerset

---

Problema con mi enfoque

No sigue la restricción de que la pregunta esté en 1 línea (adicional al encabezado de la función).

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

---

Tenía esta pregunta en mi tarea como una pregunta adicional, pero no pude hacerlo.

1. ¿Qué son las funciones de lista abstracta?

• Funciones como foldl, foldrymap

1. Mi bono incluía 3 subpartes

• La parte 1 pidió simplemente hacer esta función de la manera que quisiera. Entonces usé la recursividad para hacerlo
• La parte 2 es la parte sobre la que hice la pregunta. Este fue particularmente difícil porque había una restricción adicional del código para estar dentro de 2 líneas
• Se suponía que la tercera parte sería la más difícil.

No escriba ninguna función auxiliar y no utilice ninguna recursividad explícita (es decir, su función no puede llamarse a sí misma por su nombre). No utilice ninguna función de lista abstracta. De hecho, sólo use la siguiente lista de funciones de la raqueta, constantes y formas especiales: cons, first, rest, empty?, empty, lambda, y cond.

Sin embargo, cosa curiosa, estudié Y-combinatory pude resolver este (después de 6 horas de codificación).

Answer 1

Para responder a su parte extra 2:

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

Dos líneas, menos de 80 caracteres cada una, la primera línea reservada para define(entonces, una línea).

Si appendno está permitido, también convertimos la append ... mapcombinación en foldr:

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

o, abreviado,

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

(con exactamente 80 caracteres en su segunda línea).

Otra forma de codificar esto es el append-mapcódigo basado en-(el segundo fragmento) de esta respuesta que, cuando se vuelve a codificar foldrsolo con , se convierte en

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

o acortado,

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

que podría o no cumplir exactamente con sus requisitos.