Powerset listy używający abstrakcyjnych funkcji list

Nov 24 2020

Czy jest możliwe, aby funkcja rakiety zwracała powerety z podanej listy ?


Ograniczenia

  1. bez jawnej rekursji
  2. używać abstrakcyjnych funkcji listowych
  3. kod zawarty w 2 liniach (aktualne wymaganie)

Na przykład: (powerset '(1 2))

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

w dowolnej kolejności.

Drugie pytanie , które znalazłem, nadal używa jawnej rekursji.


Mój przepływ pracy:

  1. Biorąc (powerset '(a b c))jako przykład,
  2. Najpierw uzyskaj listę liczb całkowitych do (expt 2 (length list)) ;'(0 1 2 3 4 5 6 7)
  3. Przekształć je w odpowiednią formę binarną 2->(0,1,0). Więc mamy'((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) do listy plików binarnych. Na przykład:2->'(0,1,0)->'((0,a) (1,b) (0,c))
  5. odfiltruj wynikową listę za pomocą lambdy, tak aby zachować elementy z 1, np '((1,b)).
  6. Wyodrębnij powerset

Problem z moim podejściem

Nie podąża za ograniczeniem pytania znajdującym się w 1 linii (dodatkowo do nagłówka funkcji).

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

Miałem to pytanie w moim zadaniu jako pytanie dodatkowe, ale nie byłem w stanie tego zrobić.

  1. Co to są funkcje list abstrakcyjnych?
  • Funkcje podoba foldl, foldrimap
  1. Mój bonus obejmował 3 części
  • W części 1 poproszono o po prostu wykonanie tej funkcji w dowolny sposób. Więc użyłem do tego rekurencji
  • Część 2 to część, o którą zadałem pytanie. Ten był szczególnie trudny, ponieważ dodano ograniczenie kodu do dwóch linii
  • Część 3 miała być najtrudniejsza.

Nie pisz żadnych funkcji pomocniczych i nie używaj żadnej jawnej rekursji (tj. Twoja funkcja nie może wywołać siebie z nazwy). Nie używaj żadnych abstrakcyjnych funkcji list. W rzeczywistości, należy używać wyłącznie następującą listę funkcji rakieta, stałych i specjalnych formach: cons, first, rest, empty?, empty, lambda, i cond.

Jednak zabawna rzecz, studiowałem Y-combinatori udało mi się rozwiązać ten problem (po 6 godzinach kodowania).

Odpowiedzi

2 WillNess Nov 25 2020 at 16:57

Aby odpowiedzieć na Twoją premię część 2:

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

Dwie linie, mniej niż 80 znaków każda, pierwsza linia zarezerwowana dla define(czyli jedna linia).

Jeśli appendnie jest to dozwolone, zamieniamy tę append ... mapkombinację foldrrównież w:

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

lub skrócone,

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

(z dokładnie 80 znakami w drugiej linii).

Innym sposobem zakodowania tego jest append-mapkod oparty na tej odpowiedzi (drugi fragment) z tej odpowiedzi, który po ponownym zakodowaniu foldrtylko za pomocą staje się

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

lub skrócony,

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

które mogą, ale nie muszą dokładnie spełniać Twoje wymagania.