Powerset listy używający abstrakcyjnych funkcji list
Czy jest możliwe, aby funkcja rakiety zwracała powerety z podanej listy ?
Ograniczenia
- bez jawnej rekursji
- używać abstrakcyjnych funkcji listowych
- 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:
- Biorąc
(powerset '(a b c))
jako przykład, - Najpierw uzyskaj listę liczb całkowitych do
(expt 2 (length list)) ;'(0 1 2 3 4 5 6 7)
- 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))
- map '(1 2 3) do listy plików binarnych. Na przykład:
2->'(0,1,0)->'((0,a) (1,b) (0,c))
- odfiltruj wynikową listę za pomocą lambdy, tak aby zachować elementy z 1, np
'((1,b))
. - 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ć.
- Co to są funkcje list abstrakcyjnych?
- Funkcje podoba
foldl
,foldr
imap
- 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
, icond
.
Jednak zabawna rzecz, studiowałem Y-combinator
i udało mi się rozwiązać ten problem (po 6 godzinach kodowania).
Odpowiedzi
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 append
nie jest to dozwolone, zamieniamy tę append ... map
kombinację foldr
ró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-map
kod oparty na tej odpowiedzi (drugi fragment) z tej odpowiedzi, który po ponownym zakodowaniu foldr
tylko 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.