Conjunto de poderes de uma lista usando funções de lista abstrata

Question

É possível fazer uma função de raquete retornar o conjunto de potência de uma determinada lista ?

---

Restrições-

1. sem recursão explícita
2. usar funções de lista abstrata
3. código contido em 2 linhas (requisito real)

---

Por exemplo: (powerset '(1 2))

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

em qualquer ordem.

A outra pergunta que encontrei ainda usa recursão explícita.

---

Meu fluxo de trabalho:

1. Tomando (powerset '(a b c))como exemplo,
2. Primeiro obtenha uma lista de números inteiros até (expt 2 (length list)) ;'(0 1 2 3 4 5 6 7)
3. Converta-os em seus respectivos formatos binários 2->(0,1,0). Então nós temos'((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) para a lista de binários. Por exemplo:2->'(0,1,0)->'((0,a) (1,b) (0,c))
5. filtre a lista resultante com um lambda de forma que mantenhamos os elementos com 1, como '((1,b)).
6. Extraia o conjunto de poderes

---

Problema com minha abordagem

Ele não segue a restrição da questão estar em 1 linha (adicional ao cabeçalho da função).

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

---

Eu tinha essa pergunta na minha tarefa como uma pergunta bônus, mas não fui capaz de fazer isso.

1. O que são funções de lista abstrata?

• Funções como foldl, foldremap

1. Meu bônus inclui 3 subpartes

• A Parte 1 pediu para simplesmente fazer essa função da maneira que eu quisesse. Usei recursão para fazer isso
• A Parte 2 é a parte sobre a qual fiz a pergunta. Este foi particularmente difícil porque havia uma restrição adicional do código para estar dentro de 2 linhas
• A Parte 3 deveria ser a mais difícil.

Não escreva nenhuma função auxiliar e não use nenhuma recursão explícita (ou seja, sua função não pode se chamar pelo nome). Não use nenhuma função de lista abstrata. Na verdade, use apenas a seguinte lista de funções raquete, constantes e formas especiais: cons, first, rest, empty?, empty, lambda, e cond.

Porém, engraçado, estudei Y-combinatore consegui resolver este (após 6 horas de codificação).

Answer 1

Para responder à parte 2 do bônus:

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

Duas linhas, com menos de 80 caracteres cada, a primeira linha reservada para o define(então, uma linha).

Se appendnão for permitido, transformamos a append ... mapcombinação em um foldrtambém:

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

ou, abreviado,

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

(com precisamente 80 caracteres em sua segunda linha).

Outra maneira de codificar isso é o append-mapcódigo baseado em-(o segundo trecho) desta resposta que, quando recodificado com foldrapenas, torna-se

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

ou abreviado,

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

que pode ou não atender exatamente aos seus requisitos.